菜鳥なら誰でも理解できる毛片(KMP)アルゴリズム

まず、私のタイトル党を许して、毛片のアルゴリズムを见て毛片と何の関系もなくて、もしあなたがうっかり入ってきたら、私はほほほと言うしかありません、ほほほ^
KMPアルゴリズムは実はO(n)の文字列マッチングアルゴリズムです
A = "ababacbacab"
B = "baca"
仮定位置1から
このようにBはAの子列と言えるが、まず私たちが考えている方法はAの位置を列挙することである.例えば
1.まず位置A[1],すなわち文字'a'を列挙し,次にA[1]から「abab」が「baca」に等しいか否かを比較し,明らかに異なる
2.次に位置A[2]すなわち文字'b'を列挙し、A[2]から「baba」が「baca」に等しいかどうかを比較し、明らかに一致しない
......
試行錯誤の末、A[7]から始まる子列「baca」をBに等しく列挙した.my god、大変だった
時間の複雑さを計算してみましょう.Aの位置を列挙すると、最大O(A.length()の位置があり、各位置が最大O(B.length()に一致するので、アルゴリズムの複雑さはもちろんO(A.length(*B.length())です.
次に不思議な毛のアルゴリズムを見てみましょう
毛片アルゴリズムの考え方は,2つのポインタiとjでAとBの1つの位置を示すことである.
1)現在Aにマッチしている位置をiで表す
2)現在Bにマッチしている位置をjで表す
3)B[1...j]を満たすにはA[i+j-1...i]と等しい
ああ?理解しにくいですね.次の図(図1)は頭を叩くことができます.「ああ、頭がいいですね.簡単ですね.」
図1
灰色の部分が等しいですね^^
アルゴリズムが始まる前に、次のことを考えてみましょう.
配列pがp[j]表現を満たすことを示し、B[1...p[j]=B[j-p[j]+1...j](図3)
    
図3(画像が大きすぎて、新しいウィンドウが開きます.
灰色の2つの部分が等しい
簡単に推理して、3つの赤い部分も等しいかどうか当ててみてください(必ず理解してください.とても重要です).答えは肯定的だ
アルゴリズムは始まります:私達はこの問題を考慮して、iとjはどのように成長するべきです
①A[i+1]=B[j+1]の場合
では、私たちは2つの灰色の枠を後ろにドラッグするだけでいいですよ(図2)、そして、jがB.length()になったら、私たちのマッチング過程は終わりますよ.賢いあなたはきっと理解しますか?
図2
灰色の部分が等しいですね^^
②A[i+1]!=B[j+1]は?
iとjの定義を振り返ってみると(図1を参照すればよい)、jをp[j]に変更することができ、変更後のp[j]は図1を任意に満たすことが明らかになった.変更後、図1は次に介様マイルに拡張される(図4)
図4(図1と図3と照らしてみますよ)
jの位置を调整して、私达はまた1つの新しいjを得ました(j=p[j])、聡明なあなたは図4を読めないなら说明するしかありません...バカな私の話がまだはっきりしていないので、伝言を残して悪口を言ってください.
では、B[p[j]+1]==A[i+1]が成立するかどうかを見てみましょう.
とても楽しくあなたに教えて、ここを见て、あなたはすでにほとんどKMPアルゴリズムの全体の流れを理解して、トイレに行って先に行って、帰ってから私达は残りのステップを続けて、お茶を饮んで、ゆっくり鉴赏しましょう
お帰りなさい、ええ、続けて...
ロリーはくどくど言って、やっとコードをつけることができて、あなたはこの過程がこんなに簡単で、あなたのチタン合金の神眼を明るくして、これはプログラミングの美しさで、上!

  for (j = 0, i = 0; i < n; ++i)
  {
    while (j > 0 && B[j+1] != A[i+1]) j = p[j];//  4 
    if (B[j+1] == A[i+1]) ++j;
    if (j == m)
    {
      //  B     ，         
      cout << "    : " << i - m + 1 << endl;
      j = p[j]; //          ，                  
    }
  }

複雑度分析:まずiを観察します.A配列中のiの位置を順次スキャンしているので、iが増加していることがわかります.iはA.length()回しか増加していませんか.一方、++i,++jは寄り添う文であるため、jはせいぜいA.length()回しか増加しない.j=p[j]文はjがずっと減少していることを示している.jはA.length()回しか増加しないため、jはせいぜいA.length()回しか減少しない.そうしないと、jは負の数になっているのではないか.while(1)の内容を観察すると、jは毎回増加しないか減少していることが分かった.だから増加と減少(最外層のif elseif)の2つの文を合わせて最大2*A.length()回実行するので、この時間は複雑度でもちろんO(A.length()です.
賢いあなたはきっと私たちにもう一つの問題があることに気づいたに違いない.つまり、配列Pを指示することだ.PがO(B.length()でできることを教えてあげますか?
p[1]を知っているとしたら...p[j]はいくらですか.私たちはどのようにp[j+1]を構築しますか.ええ、私は口が乾いて舌が乾いて、よだれを飲んでゆっくりして、前の図が先です(図5)
図5(保存したほうがいいです.図が大きすぎて、穴のお父さんのcsdnはスクロールバーがありません!!)
あなたが上の図をよく観察した后に私は多く说明しなくてp[j+1]の构造の过程を知ることができることを信じて、あなたはただp[j]の定义をはっきりさせるだけで、すべての问题はすべてとても楽にKOして落ちます
p構築プロセスのソースコードは以下の通りである.

  p[1] = 0;
  for (j = 1; j <= m - 1; ++j)
  {
    k = j;  
    while (k > 0 && B[j+1] != B[p[k]+1]) k = p[k];
    p[j+1] = (k!=0 ? p[k]+1 : 0);
  }

最後に、完全なソースコードを放出します.

#include 
#include 
using namespace std;

int main() {
  string A = " ababababafcbaababafcc";
  //string A = " ababafcc";
  string B = " ababafcb";
  int p[20];
  int n = A.size() - 1;
  int m = B.size() - 1;
  int i, j, k;

  p[1] = 0;
  for (j = 1; j <= m - 1; ++j)
  {
    k = j;
    while (k > 0 && B[j+1] != B[p[k]+1]) k = p[k];
    p[j+1] = (k!=0 ? p[k]+1 : 0);
  }


  //    
  for (j = 0, i = 0; i < n; ++i)
  {
    while (j > 0 && B[j+1] != A[i+1]) j = p[j];
    if (B[j+1] == A[i+1]) ++j;
    if (j == m)
    {
      cout << "    : " << i - m + 1 << endl;
      j = p[j];
    }
  }
  return 0;
}

matrix 67大神の文章に感謝しますhttp://www.matrix67.com/blog/archives/115