KMP 文字列照合

KMP は、不一致が起きてもテキストのカーソルを戻さずにパターンを探す。先にパターンの LPS 表を作り、既に一致した部分の接頭辞と接尾辞の重なりを保持する。前処理 O(m)、検索 O(n)、補助空間 O(m) となる。

テキストの下に透明なパターンの帯を置くと考える。不一致なら、安全な重なりまで帯を動かし、既知の接頭辞を一致済みの接尾辞に合わせる。現在のテキスト文字は動かさない。どの一致を残せるかを LPS 表が決める。

KMP が役立つ場面

通常の部分文字列検索は言語の組み込み関数で足りる。巻き戻せない socket、パイプ、ファイルの分割入力や、最悪 O(n + m) の保証が必要な場面では KMP が使える。パターンを一度前処理し、チャンクをまたいで j を保持すれば、通過したテキストを捨てられる。

KMP の仕組み

LPS は、接尾辞でもある最長の真の接頭辞の長さを表す。「真の」は文字列全体を除くという意味だ。ABABA の最長の重なりは ABA なので値は 3。

各パターン位置に LPS 値を作る。k は計算中の位置、len は検討中の境界長。pattern[k] == pattern[len] なら長さを一つ増やして lps[k] に書く。不一致で len > 0 なら len = lps[len - 1] とし、短い境界で同じ pattern[k] を再試行する。このとき k は進めない。境界が残らなければ 0 を書いて k を進める。

検索では i がテキスト、j がパターンを指す。一致なら両方を進める。不一致で j == 0 なら i だけを進める。j > 0 なら j = lps[j - 1] として同じ text[i] を再試行する。

3 文字を残し、2 位置動かす

LPS は保持する長さで、移動量ではない。j が 5 から 3 になると、三文字の一致を残し、帯を 5 - 3 = 2 位置動かす。

テキストのカーソルが戻らないことと、各文字を一回だけ比較することは違う。フォールバックでは i を固定し、一文字を複数のパターン位置と比較できる。線形時間は前進と後退の合計に上界があることから導かれる。

KMP のステップ

既定のテキストは ABABABACA、パターンは ABABACA。

1. lps[0] = 0。一文字の A に非空の真の接頭辞はない。
2. 添字 1 の B は A と異なり、短い境界もないので lps[1] = 0。添字 2、3、4 の A、B、A が重なりを伸ばし、値は 1、2、3 となる。
3. 添字 5 の C は長さ 3 の境界の次の文字と合わない。len を 3 から lps[2] = 1 に下げ、同じ C を再試行する。まだ合わず、lps[0] = 0 へ下げ、最後に 0 を書く。この間、添字 5 は動かない。
4. 添字 6 の A は先頭と合い、lps[6] = 1。表は [0, 0, 1, 2, 3, 0, 1] になる。
5. i = 0, j = 0 から検索し、最初の五組 ABABA が一致して i = 5, j = 5 になる。
6. text[5] は B、pattern[5] は C で不一致。lps[4] = 3 を読み、j を 5 から 3 に下げる。ABA を残して帯を二位置動かし、i は 5 に保つ。
7. 同じ text[5] を pattern[3] と比べると B が一致する。続く A、C、A も合い、i = 9, j = 7 で終了する。開始位置は i - j = 2。

advance i (bug) はフォールバックだけを変更し、j = lps[j - 1] の後で i も増やす。添字 5 の B を再試行せず飛ばすため、添字 2 に本物の一致があっても、テキストを使い切って -1 を返す。

時間計算量と空間計算量

テキスト長を n、パターン長を m とする。

前処理の各反復は k を進めるか len を短くする。短縮の合計は、それまで伸びた量を超えない。検索も i を進めるか j を短くし、j が戻れる総距離は、それまで増えた量に制限される。テキストをリセットして全走査し直すことはない。LPS 配列は O(m)、カーソルとカウンターは O(1)。

境界ケース

• 空テキストと非空パターンでは -1 を返す。
• パターンが長すぎると、途中まで一致してもテキストが尽きて -1 になる。
• 一文字パターンの LPS は [0] で、その文字を走査する検索になる。
• AAAA の LPS は [0, 1, 2, 3]。後の不一致で i を固定したまま何度も戻る場合がある。
• 重なる一致には LPS が役立つ。本実装は最初の一致を返す。全件検索なら記録後に j = lps[j - 1] として続ける。
• 空パターンは API ごとに規約が違うため、本レッスンでは拒否する。本番実装は pattern[0] を読む前に動作を決める。

よくある間違い

• LPS を移動量として使う。j = lps[j - 1] とし、移動量は j の減少量から求める。
• j > 0 のフォールバック後に i を増やし、現在の文字を飛ばす。誤り版は添字 2 の一致を見逃す。
• 表の構築中、フォールバックで k も進め、短い境界を現在の文字で試さない。
• 不一致ごとに j をゼロにして既知の重なりを捨てる。正しさを保つには再配置も適切に行う必要があり、KMP の代入と単純には置き換えられない。
• 文字列全体を真の接頭辞に含める。各接頭辞が自分自身を最長境界とし、表が役立たなくなる。
• 各テキスト文字を一回だけ比較すると説明する。実際の不変条件は、i を減らさず、正の長さから戻る間も増やさないことだ。