模式匹配

Question

我实现了一个简单的模式匹配算法。对优化有什么建议吗？

 #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;
     }
 }

Answer 1

布尔答案:您的函数返回int，但它只返回0或1。在这里，bool更合适。

早期返回:一旦您找到“模式”，return。其他每一次事件都会保留found true，所以您只需快速退出即可。

早期中断:一旦您注意到某个字符不匹配，break。你不需要检查剩下的，比赛已经坏了。您也不需要计算匹配的字符数。一个布尔值就足够了。

如果我们应用这三种方法，我们最终会

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;
}

但是，除非您要获得最后一点的性能，否则最好使用标准库来发挥您的优势：

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

Answer 2

您应该重命名该函数。当我阅读单词模式时，我会想到带有占位符的字符串，比如*.txt或(\d+)-(\d+)-(\d+)。您的代码没有这样做，它只是搜索一个确切的字符串。函数名应该反映这一点。

这样做的一个好的副作用是，通过上面的重命名消除了错误的patten。