string - 查找字符串的子字符串的出现？为什么我的程序不打印任何匹配项？

Question

最近我接到了一个任务，要查找一个字符串在另一个字符串中出现的次数，类似于 ctrl + f 的工作原理。下面是我的实现，但我正在检测代码中的错误。

#include<iostream>

using namespace std;

int findsubstr(string s, string substr);

int main(){
    string a = "abcxyzcxy";
    string b = "cxy";
    cout << "number of matching found " << findsubstr(a, b) << endl;
    return 0;
}
int findsubstr(string mainstring, string substr){
    int i;
    int count = 0;
    if(substr.length() > mainstring.length()){
        cout << "invalid string for matching!" << endl;
        return 0;
    }
    for( i=0; i<mainstring.length(); i++){
        int j;
        for (j=0; j<substr.length(); j++){
            if(mainstring[i+j] != substr[j]){
                break;
            }
        }
        if(j==substr.length()-1){
            cout << "pattern found at " << i << endl;
            count++;
        }
    }
    return count;
}

我在网上找到的代码几乎完全相同，但我的程序似乎从未找到匹配项，即使有一个。上面的例子有两个。我的逻辑是将 i 作为主字符串的索引，将 j 作为子字符串的索引。然后，如果子串中的所有字符都匹配主串中以 i 开头的字符，则在该索引处找到模式。

Answer 1

for(i = 0; i <= mainstring.length()-substr.length(); i++){
    int j;
    for (j = 0; j < substr.length(); j++){
        if(mainstring[i+j] != substr[j]){
            break;
        }
    }
    if(j == substr.length()){
        cout << "pattern found at " << i << endl;
        count++;
    }
}

您的逻辑是正确的，但问题是 j 在最后一次迭代中增加到 pattern 的长度。您的程序在最坏情况下的运行时间为 O(mn)，其中 m 是模式的长度，n 是您尝试在其中查找模式的字符串的长度。

在实际应用中，ctrl+f使用了更优化的算法，在文本很大的情况下大大减少了运行时间。这里wiki有一个很好的此类算法列表。

以KMP为例，假设你有一个文本s = ababac和pattern m = abac，你会发现s[3]、b 和 m[3]、c。但是，我们知道 abab 中的 ab 是 abac 中的前缀，所以我们可以跳过检查 ab模式并查找 ac，但是，这需要经过预处理的查找表。