發現字符串的子字符串的發生？爲什麼我的程序不打印任何匹配？

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