2
\$\begingroup\$

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;
     }
 }
\$\endgroup\$
5
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.