文字列照合アルゴリズム（KMP・Boyer-Moore・Rabin-Karp）

素朴照合がなぜ遅いのか

長さ n のテキスト T から長さ m のパターン P の出現位置を探すのが文字列照合です。素朴（ナイーブ）な方法は、開始位置を 0 から n-m まで1つずつずらし、各位置で先頭から文字を突き合わせます。計算量記法に不安があれば計算量と Big-O 記法を先に確認してください。

naive(T, P):
  for s in 0..n-m:
    j = 0
    while j < m and T[s+j] == P[j]:
      j += 1
    if j == m: report match at s

問題は不一致が起きたときの挙動です。素朴法は s を 1 進めてまた j=0 から照合し直す。直前に j 文字一致していたという情報を丸ごと捨てるため、T = aaaaab、P = aaab のような入力では各位置でほぼ m 回比較し、最悪 O(nm) になります。3つの古典手法は、いずれも「一度得た一致・不一致の情報を再利用してずらし幅を稼ぐ」という同じ思想を、別々の道具で実現します。

KMP: 失敗関数で先頭に戻らない

KMP（Knuth-Morris-Pratt）の核心は、テキスト側の添字を決して戻さない点です。位置 s で j 文字一致した後に不一致が起きたとき、一致済みの P[0..j-1] の中身は分かっています。この情報から「次にどこから照合を再開してよいか」をパターンだけから前計算しておくのが失敗関数（failure function、別名 LPS 配列）です。

fail[j] を「P[0..j-1] の真の接頭辞かつ接尾辞になっている最長の文字列の長さ」と定義します。たとえば P = abcabd なら、abcab の接頭辞と接尾辞が一致する最長は ab で長さ 2。不一致時はこの長さまで j を巻き戻すだけで、テキストの添字 i は進めたままにできます。

build_fail(P):       # 前処理 O(m)
  fail[0] = 0; k = 0
  for j in 1..m-1:
    while k > 0 and P[j] != P[k]: k = fail[k-1]
    if P[j] == P[k]: k += 1
    fail[j] = k

kmp(T, P):           # 照合 O(n)
  j = 0
  for i in 0..n-1:
    while j > 0 and T[i] != P[j]: j = fail[j-1]
    if T[i] == P[j]: j += 1
    if j == m: report match; j = fail[j-1]

なぜ線形になるのか。照合ループで i は単調に増え続け、巻き戻すのは j だけ。j は1回の一致で高々 +1 しか増えないので、while での減少の総回数も全体で n を超えません。前処理 O(m) と合わせて最悪でも O(n+m) が保証され、しかもテキストを読み直さないので入力ストリームにも向きます。失敗関数の考え方は正規表現エンジンの内部のオートマトン構築とも地続きです。

Boyer-Moore: 右端から照合してスキップする

Boyer-Moore はパターンを右端から左へ照合する点が逆転の発想です。末尾で不一致が起きたとき、2つの規則で一気にスキップします。

• 不一致文字規則（bad character）: 不一致になったテキスト文字 c がパターン内で最後に現れる位置までずらす。c がパターンに含まれないなら、パターン全体を c の次まで飛ばせる。
• 好接尾辞規則（good suffix）: すでに一致した末尾部分（接尾辞）が、パターン内の別の場所に再出現する位置までずらす。再出現がなければ大きく飛べる。

実際の実装は両規則のうちずらし幅が大きい方を採用します。鍵は「テキストの文字を1つも読まずに飛ばせる区間がある」こと。アルファベットが大きく（自然言語など）パターンがある程度長いほど、平均で1文字あたり1回未満の比較で進み、実測では最速級になります。これが多くのテキスト検索ツール（grep 系）で採用される理由です。

ただし最悪計算量には注意が要ります。不一致文字規則だけの簡易版（Boyer-Moore-Horspool）は最悪 O(nm) に退化し得ます。好接尾辞規則を併用した完全版でも、線形を保証するには Galil 規則のような追加の工夫が要ります。「実測は速いが、最悪保証は素朴ではない」という性質を押さえてください。

Rabin-Karp: ローリングハッシュで複数同時探索

Rabin-Karp は照合をハッシュ比較に置き換えます。パターンのハッシュ値を1つ計算しておき、テキスト側の長さ m の窓を1つずつずらしながら、窓のハッシュとパターンのハッシュを比べる。ハッシュが一致したときだけ、念のため実際の文字列を1文字ずつ照合します。ハッシュの基礎はハッシュテーブルの内部も参考になります。

素朴にやると各窓のハッシュ計算に O(m) かかり意味がありませんが、ローリングハッシュが効きます。窓を1つ右にずらすとき、先頭の1文字分の寄与を引き、末尾に新しい1文字分の寄与を足すだけで、次の窓のハッシュを O(1) で更新できます。多項式ハッシュ h = (c0·b^(m-1) + c1·b^(m-2) + … + c_{m-1}) mod q を使うと、この差分更新が定数時間で書けます。

rabin_karp(T, P):
  hp = hash(P); ht = hash(T[0..m-1])
  bm = b^(m-1) mod q
  for s in 0..n-m:
    if ht == hp and T[s..s+m-1] == P:   # 衝突確認は実比較で
      report match at s
    if s < n-m:                          # 窓を1つずらす
      ht = ((ht - T[s]*bm)*b + T[s+m]) mod q

良いハッシュ（大きい素数 q と適切な基数 b）を選べば偽一致（衝突）はまれで、期待計算量は O(n+m)。ただし衝突が多発する病的入力では実照合が頻発し最悪 O(nm) に落ちます。最大の利点は別にあります。複数のパターンを同時に探す用途で、各パターンのハッシュを集合に入れておけば、窓のハッシュを1回計算するだけで全パターンを照合できる。盗用検出や多数のシグネチャ照合で Rabin-Karp が選ばれるのはこのためです。

三手法の比較と選び方

ここで σ はアルファベットの大きさです。選択の起点は「どの前提を守りたいか」に尽きます。

• 最悪計算量を確実に線形に抑えたい／テキストを読み直せないストリーム処理 → KMP。挙動が単純で予測可能。
• 単一パターンで実測スピード重視、英文など文字種が多い → Boyer-Moore 系。多くの検索ツールの既定。
• 多数のパターンを一度に探す、または2次元・部分文字列のハッシュ照合 → Rabin-Karp。ローリングハッシュの汎用性が効く。

いずれも素朴法の「比較結果を捨てる」無駄を、失敗関数・スキップ規則・差分ハッシュという別の道具で潰している点は共通です。「どれが速いか」ではなく「この入力（文字種・パターン数・最悪保証の要否）で何を守りたいか」から選ぶのが、曖昧さのない判断基準になります。