KMP文字列検索、失敗関数でO(n+m)にパターンを見つける - AlgoNote

KMPとは？

KMP(Knuth-Morris-Pratt)は、長いテキストでパターン文字列が現れる位置をO(n+m)で見つける文字列検索アルゴリズムです。1文字ずつずらして毎回最初から比較する単純検索のO(nm)の非効率を、「比較して既に分かった情報」を再利用して取り除きます。

核心の一行: 「不一致でもテキストを戻さない」。 パターンだけ適切な分ジャンプさせればよいのです。

核心: 失敗関数(部分一致テーブル)

パターン自身を分析し、各位置ごとに「接頭辞であり同時に接尾辞でもある最長部分の長さ(LPS)」を前もって求めておきます。

パターン途中で不一致が出たら、このLPSの分だけパターンを前へジャンプさせます。既に一致した接頭辞が再び使える位置へ正確に移すので、最初から比較し直す必要がありません。

なぜ速いのか？

単純検索は不一致のたびにテキストポインタを1つ戻して再開します。KMPはテキストポインタを決して戻さず前へのみ進みます — 戻すべき情報を失敗関数が既に持っているからです。だからテキストをちょうど一度走査してO(n)、失敗関数の計算がO(m)で、全体O(n+m)です。

動作原理

ステップ1. パターンから失敗(LPS)配列を作ります。

ステップ2. テキストを一度走査し、パターンと比較します。

ステップ3. 文字が一致すればテキスト・パターンの両ポインタを進めます。

ステップ4. 不一致ならパターンポインタを LPS 値へジャンプ(テキストポインタはそのまま)、パターンが先頭ならテキストのみ1つ進めます。

ステップ5. パターン末尾まで一致すれば1回発見で、再びLPSでジャンプして次の出現を探します。

AlgoNoteの可視化は、不一致時にパターンがどこへジャンプし、テキストポインタが動かないかをステップごとに示します。

時間計算量と空間計算量

nはテキスト長、mはパターン長です。

例で追ってみる

テキスト ABABABCA、パターン ABABC:

• •ABAB まで一致し、C vs A で不一致
• •単純検索ならテキストを戻して再開するが、KMPはLPSを見てパターンだけジャンプ
• •既に一致した AB を再利用し、テキストポインタを保ったまま続行

よくあるミス

• •失敗関数のバグ: LPSの計算がKMPの半分です。「真接頭辞であり真接尾辞でもある最長長」を正確に実装しましょう。
• •テキストの戻し: テキストポインタを戻すとO(nm)に退化し、KMPの意味がなくなります。
• •ジャンプ後の処理: パターンポインタが0でも不一致なら、テキストのみ進めて無限ループを避けます。

AlgoNoteで直接確認しましょう

不一致が出たときパターンが失敗関数の分ジャンプし、テキストポインタが戻らない過程をAlgoNoteでステップごとに確認できます。

KMPの可視化へ →