Pattern matching

Question

I have implemented a simple pattern matching algorithm. Any suggestions for optimization?

 #include<iostream>
 #include<string>

 int patten_search(const std::string &txt, const std::string &pat) {
     int found = 0;
     for (int i = 0; i<txt.size()-pat.size()+1; i++) {
         int lps = pat.size();
         for(int j=0; j<pat.size(); j++){
             if(pat[j] != txt[i+j])
                 lps --;
         }
         if(lps == pat.size()){
             i = i+lps;
             found = 1;
         }
     }
     return found;
 }


 int main() {
     std::string txt;
     std::string pat;
     std::cout<<"enter your text string"<<std::endl;
     std::cin>>txt;
     std::cout<<"enter your pattern which you would like to search"<<std::endl;
     std::cin>>pat;
     if(patten_search(txt, pat)){
         std::cout<<"Pattern found"<<std::endl;
     } else {
         std::cout<<"Pattern not found"<<std::endl;
     }
 }

Zeta · Accepted Answer · 2017-10-22 11:19:56Z

Boolean answers: Your function returns int, but it only return 0 or 1. A bool is more appropriate here.

Early returns: As soon as you found the "pattern", return. Every other occurrence will keep found true, so you can just take a quick exit.

Early breaks: As soon as you notice that a character does not match, break. You don't need to check the rest, the match is already broken. You also don't need to count the number of characters that match. A single boolean is again enough.

If we apply those three, we end up with

bool patten_search(const std::string &txt, const std::string &pat) {    
    for (int i = 0; i < txt.size() - pat.size()+1; i++) {
        bool failed = false;
        for(int j = 0; j<pat.size(); j++){
            if(pat[j] != txt[i+j]) {
                failed = true;
                break;
            }
        }
        if(failed == false){
            return true;
        }
    }
    return false;
}

However, unless you're going for the last bit of performance, it's a better idea to use the standard library to your advantage:

bool patten_search(const std::string &txt, const std::string &pat) {    
    return txt.find(pat) != std::string::npos;
}

Roland Illig · Accepted Answer · 2017-10-22 23:20:54Z

1

You should rename the function. When I read the word pattern, I think of a string with placeholders, such as *.txt or (\d+)-(\d+)-(\d+). Your code doesn't do any of this, it just searches for an exact string. The function name should reflect that.

A nice side effect of this is that the typo patten is eliminated by the above renaming.

answered Oct 22, 2017 at 23:20

Roland Illig

21.9k2 gold badges36 silver badges84 bronze badges

Add a comment |

Stack Exchange Network

Pattern matching

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Pattern matching

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions