发现字符串的子字符串的发生？为什么我的程序不打印任何匹配？

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

我在网上找到的代码几乎是相同的，但我的程序似乎从来没有找到一个匹配，即使有一个。上面的例子有两个。我的逻辑是让我作为mainstring的索引和j作为子串的索引。那么如果来自子字符串的所有字符都匹配从主要字符串开始的字符，则在该索引处找到模式。

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递增图案上的最后一次迭代的长度。 您的程序的运行时间最差的情况是O（mn），其中m是模式的长度，n是您尝试查找模式的字符串的长度。

在实际应用中，ctrl + f使用更优化的算法，大大减少文本巨大时的运行时间。这里wiki有这样算法的一个好名单。

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

Answer 2

这只是因为你正在比较j与substr.length（） - 1。

当它匹配时，j已经变成了substr.length（）。所以你应该使用substr.length（）进行比较。以下是完整的程序。

#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()){ 
      cout << "pattern found at " << i << endl; 
      count++; 
     } 
    } 
    return count; 
}