KMP パターン検索ステップカウンター | 失敗関数テーブルとステップ削減を可視化

Knuth-Morris-Pratt 法が自分のテキスト上でどう動くかを観察するツール。パターンの LPS 失敗関数テーブルを構築し、線形時間の KMP 走査を実行して、同じ入力に対する素朴な二重ループ探索と比較ステップ数を並べて表示。

💡 このツールについて

KMP の解説の多くは「計算量は O(n+m)、以上」で終わる。これだと計算量の式は唱えられても、削減がどこで効いているのか、失敗関数がなぜ必要なのかが体感として腑に落ちない。授業の課題やコーディング面接で実装しようとすると、まさにこの LPS テーブルでつまずく人が多い。

このカウンターは、自分の入力から出る具体的な数値でその溝を埋める。任意のパターンとテキストを入力すると、LPS 配列が i / p[i] / lps[i] の行ごとに見え、正確なマッチ位置と、両手法の比較回数が並ぶ。KMP と素朴の数値は同じ対象テキストから出るので、損益分岐点を自分で見つけられる。ランダムなテキストでは差は小さいが、a が続くテキストに対する aaaab のようなパターンでは素朴探索が膨れ上がる一方、KMP は線形のまま。この対比こそアルゴリズムの核心で、ここでは好きなだけ再現できる。

🧐 よくある質問

LPS テーブルには何が格納されている? LPS[i] は p[0..i] の「真の prefix かつ suffix である最長の長さ」。不一致時に KMP はパターン側のポインタを 0 に戻さず LPS[j-1] へジャンプし、これが冗長な比較を消す仕組み。

ここでの「比較」の数え方は? 1 ステップ = パターン 1 文字とテキスト 1 文字の比較 1 回。KMP が LPS テーブル経由で行うポインタ巻き戻しはテキスト文字に触れないため、ステップに数えない。素朴探索は内側ループの全文字比較を数える。

速度比が 1x を少し超える程度なのはなぜ? 自然言語やランダムなテキストでは不一致が先頭文字で起きやすく、素朴探索は深く後退しない。KMP の優位は、長い反復 prefix を持つパターンを敵対的なテキストに当てたとき、つまり素朴探索が同じ文字を何度も再走査する場面で現れる。

重なるマッチも検出する? する。完全一致後に KMP は j を LPS[m-1] に戻すため、aaaa の中の aa のような重複出現もすべて報告。マッチ位置は 0 始まり。

空白や記号も区別する? 区別する。文字単位の検索なので空白・改行・記号もそのまま照合。両欄とも長さ制限はないが、短いパターンほど LPS テーブルの構築は速い。

📚 豆知識

KMP は 1977 年に Donald Knuth・James Morris・Vaughan Pratt が発表。線形時間の着想は Morris がテキストエディタを作る過程で先に見つけ、後に Knuth がオートマトン理論で定式化したという経緯が伝わる。失敗関数は、パターンからコンパイルされた小さな有限状態機械とも言える。この prefix function の発想は文字列探索を離れても現れ、文字列の相異なる border の数え上げや、反復列の最短周期を求める競技プログラミングの定石を支えている。