KMPアルゴリズムのジャンプがエラーを起こしやすいですか？

Question

はの例を考えてみましょう： この例では、テキスト= "AABCAABDCAAB"、 パターン= "AABCAAB"

、パターンがインデックスに一致します= 0
AABCAAB DCAAB
AABCAAB

KMPアルゴリズムによれば、j =パターン長さのとき、一致を検出し、j = lps [パターン長-1] = 3をリセットすると、パターン[j] = 'C'を意味する。

アルゴリズムは、ジャンプした：
AABCAAB D CAAB
_____AAB C AAB

例えば、ジャンプの間のケースを考慮することなく：
AABCAABDCAAB
_AABCAAB

AABCAABDCAAB
__AABCAAB
...

この場合、いくつかの試合を見落とすことは可能ですか？

Answer 1

KMPアルゴリズムはすべてのケースで正しく動作することが証明されています。その背後にある主な考え方は、パターンの最初のk文字に一致すると、それらのk文字に正確に一致するため、k文字の文字が分かることです。シフト・テーブルは、k文字に一致したときに使用されるシフトが、それらのk文字の知識があれば、安全に行えるように計算されます。

例では、AABCAABと一致しているので、テキストはAABCAABです。あなたがちょうどマッチしたパターンにはCが1つしかないので、マッチするのに使用されたCが次に試行されたマッチでパターンのどの部分にも重ならないようにパターンを移動させなければなりません。次の試行された試合の位置を示します。

（私はKMPアルゴリズムは、通常は説明していないパターンの不規則なシフトを作るとしてではなく、検索対象のテキストに沿って定期的にステッピングと、これまでにマッチしているどのように多くのパターンの文字ワークアウトで証明されることに注意してください。ので、すべての場合に機能することがわかっているアルゴリズムの見解を使用した証明があります）。