文字列アルゴリズムの可視化

素朴な部分文字列探索は、不一致でパターンを一つずらしてやり直します。効率的な方法は、接頭辞と接尾辞の関係、現在窓の指紋、将来の複数問い合わせ用の索引を保存します。

KMP は一致済みの接尾辞がパターンの接頭辞でもあることを使い、テキスト位置を戻しません。Rabin-Karp は窓の指紋を移動ごとに更新します。接尾辞配列は全接尾辞の開始位置を先にソートし、後の問い合わせを二分探索にします。

三つの再利用方法

方法保存する状態前処理一問い合わせ
KMPLPS 表の接頭辞・接尾辞一致長O(m)O(n + m)
Rabin-Karpパターンと窓の指紋O(m)期待 O(n + m)、最悪 O(nm)
接尾辞配列辞書順の接尾辞開始位置本例 O(n log^2 n)O(m log n)

KMP はパターンを前処理し、決定的な線形上界を持ちます。Rabin-Karp は窓の再利用を示しますが、同じハッシュでも文字の一致確認が必要です。接尾辞配列は重い準備を払い、同じテキストへの多数の問い合わせで役立ちます。

推奨する学習順序

KMPの LPS 表で、不一致後にどの一致を残せるかを確認します。テキスト位置は固定したまま、パターン側の一致長が戻ります。誤った版はここでテキストを進め、実際の出現を見逃します。

Rabin-Karpは固定幅の窓を一つずつ進めます。出ていく数字を式から除き、新しい数字を加え、中間を読み直さず更新します。既定例の 31428 と 31415 は法 13 で同じハッシュですが、文字確認が前者を拒否します。

接尾辞配列の BANANA では、繰り返す接頭部分の比較を、倍増法で整数ランクの対へ変えます。開始位置が辞書順になった後、ANA を lower-bound の二分探索で探します。

注目する点

  • KMP で残す長さとパターンの移動距離は、関連していても別の量です。
  • Rabin-Karp でパターン行が消えるのは、異なるハッシュにより窓の文字比較をすべて省ける場面です。
  • 接尾辞配列の終端番兵 -1 は、見える接頭部分が同じでも A を ANA より前へ置きます。
  • 失敗例で一行や前提が変わったとき、再利用の規則がなぜ破れるかを確認します。

文字列アルゴリズムの可視化一覧

入力を変え、Python または JavaScript のコードとトレースを並べて確認してください。

KMP 文字列照合不一致後も接頭辞と接尾辞の境界を再利用し、テキストを再走査せず O(n + m) で照合する。Rabin-Karpローリングハッシュでパターンを探し、文字より先に指紋を比べる。接尾辞配列すべての接尾辞を配列にソート——1つのテキストへの高速な部分文字列クエリ。