KMPパターン検索アルゴリズム

Question

私はKMPアルゴリズムを理解していました。接尾辞と接尾辞を対応付けるための値を格納し、文字列を検索するときに戻ってこないという概念は、パターン "abcdabca"接頭辞配列は{0、 0,0,0,1,2,3,1} {0,0,0,0,1,2,3、_}まで理解してから4番目の位置の 'd'が 'a ' やっと。そして、algoは、j！= 0ならばarr [j-1]に戻ると言うが、これが正しい結果をもたらすことがわかるが、私はなぜ前の要素[data]に戻るのかわからない理解基盤。

一致する要素またはj == 0が見つかるまで戻ってきますが、なぜ私たちが戻ってくるのかを理解する方法は見つけられません。私自身の理解で

おかげ

Answer 1

は、我々は、サブ文字列S[0...i]の接尾辞と同じである最長プレフィックスの0から始まるインデックス（最長ために、私が最も長いことを意味する表現するために、障害の機能F[i]を使用します全体の部分文字列そのもの以外）

あなたのOPから、私はあなたの実装やチュートリアルでは、1ベースを使用していると思うが、それは完全に次の例を検討し、実装

に依存します：S = abababcabab

を

障害機能を使用すると、慎重に見てアルゴリズムが故障S' = ababab????のための機能とF = [-1,-1,0,1,2,3,?,?,?,?,?]

今、次の文字がcで計算終了時にあるときに何が起こっているかであることが何F = [-1,-1,0,1,2,3,-1,0,1,2,3]

ようになりますアルゴリズムは、すでに知られている最も長い接頭辞（接尾辞）ababに長い方を加えることができるかどうかをテストします。テストはプレフィックスababa！=接尾辞ababcとして失敗しますが、それは何ですか？

その後、アルゴリズムが失敗した最長プレフィックス（サフィックス）の最長プレフィックス（サフィックス）を見てみてください、はい、それが答えである場合について、その上のcを保留することは（私たちに試合を与えるかを確認します）。

これはアルゴリズムがabあるababの最長プレフィックス（サフィックス）をテストすることを意味し、我々は（我々はcを追加するためにテストし、失敗した）F(abab) = 3を知っていると我々はF(F(abab)) = F(3) = 1を知っているので、我々はすぐにそれを知ることができ、 abの位置です。

同じことが再帰的に起こります。これは、一致が見つかったとか、まったく一致がなくなるまでです。 F[]の "ジャンプ"はこのプロセスを実装しています。次の潜在的な最長プレフィックス（接尾辞）を試してください。失敗した場合は、次のものを見つけてください...