文字列の部分文字列の出現を見つけるか？なぜ私のプログラムは一致するものを印刷しないのですか？

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

私がオンラインで見つけたコードはほぼ同じですが、私のプログラムは一致しているとは思われませんでした。上記の例は2つです。私の論理は、私がメインストリングのインデックスとして、サブストリングのインデックスとして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が最後の繰り返しのパターンの長さにインクリメントされていることです。 あなたのプログラムは、mは、パターンの長さであり、nはあなたがでパターンを検索しようとした文字列の長さであるO（MN）の時間を実行している最悪のケースを持っています。

実際のアプリケーションでは、CTRL + fは、テキストが巨大なときに実行時間を大幅に短縮する、より最適なアルゴリズムを使用します。ここではwikiにこのようなアルゴリズムの素敵なリストがあります。

KMPは、例えば、テキストs = ababacとパターンm = abacがあると、あなたはs[3]、bとm[3]、cの間に不一致があります。しかし、abのababは接頭辞がabacであることがわかっているので、のパターンを調べずに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; 
}