文字列マッチング
01 / 共通の仕組み
テキスト T の中にパターン P を見つける —— 素朴な O(N·M) を 3 つのサブパターンすべてが O(N + M) に落とし込む。 共通の手口はパターンの構造情報を事前計算すること。 不一致のたびに走査が冗長な比較をスキップできるようにする。 違うのは何を事前計算するかだけ:失敗関数(KMP)、ローリングハッシュ(Rabin–Karp)、 連結文字列上の前缀マッチ配列(Z)。
01 / 一文での本質
失敗関数は、パターンが既に何文字分の接尾辞と一致しているかを教えてくれる —— だから不一致時はそこへジャンプし、最初から比較し直さない。パターンを一度前処理し、テキストを一度走査する、両方とも線形。
問題T の中の P の全出現位置P"abab"T"ababcabababd"
パターン P は 4 文字、テキスト T は 12 文字。まず P 上で失敗関数を構築し、それを使って T を走査する。
ステップ
0 / 23
i
—
j
—
一致数
—
0 / 23
02 / パターンの骨格
# P 上で fail[] を構築 — 最長の真前缀かつ後缀fail[0] ← 0; k ← 0for i in 1..M-1:while k > 0 and P[k] ≠ P[i]:k ← fail[k-1] # 鍵となるジャンプif P[k] == P[i]: k ← k + 1fail[i] ← k# fail[] を使ってテキスト T を走査j ← 0for i in 0..N-1:while j > 0 and P[j] ≠ T[i]:j ← fail[j-1]if P[j] == T[i]: j ← j + 1if j == M: # i で一致、続行:record(i − M + 1); j ← fail[j-1]
03 / このパターンを使うべき合図
「パターンの全出現位置を求める」
典型的な用途。O(N + M) の strstr / indexOf —— ハッシュも確率も不要、 一致は確定、不一致も確定。LC 28 を一回の走査で。
「繰り返し部分文字列の周期」
LC 459。長さ
n の文字列が部分文字列の繰り返しになるのは、n − fail[n−1] が n を割り切るとき —— それが最小周期。 失敗関数自体に周期情報が含まれている、無料で。「先頭に追加して最短回文」
LC 214。
s + "#" + reverse(s) 上で失敗関数を作ると、 末尾の fail[] 値が s の最長回文前缀になる。残りを反転して前に貼る —— 線形時間。「最長 happy 前缀」
LC 1392。「happy 前缀」とはまさに入力文字列上の
fail[n−1] —— 定義どおり「真前缀かつ真後缀」の最長値。KMP の前処理ステップがそのまま答え。04 / よくある落とし穴
i.
fail[k] を使ってジャンプしてしまう(正しくは fail[k−1])。最も多いオフバイワン。不一致後、欲しいのは「次に一致しうる最長の前缀」—— つまり直前に一致していた長さに対応する失敗値、
fail[k−1] であって fail[k] ではない。 誤ると無限ループに陥るか、正当な一致をひっそりと取りこぼす。ii.
完全一致後に
j をリセットし忘れる。j == M になったら、i を進める前に必ず j ← fail[j−1] を実行する。さもないと重なり合う出現を取り逃す。 パターン "aaa" はテキスト "aaaaa" に 3 回現れる、1 回ではない。iii.
「前缀関数」と「next 配列」の混同。
2 つの教え方:前缀関数
fail[i] は i で終わる前缀の LPS 長を返す; 古典的な next[i] は長さ i の前缀の LPS を返す(全体に 1 ずれる)。 教科書によっては 0 番目に −1 を入れる流儀もある。同じアルゴリズム、異なるインデックス —— 一つの流儀に統一する、特に他所からコードを移植するときは要注意。05 / LeetCode で練習
4 問。最初の 1 問は教科書的な用途、残りの 3 問は同じ失敗関数の応用 —— 周期検出、回文構築、LPS そのものが答え。
— / どれをいつ使うか
KMP
パターンが固定で、決定的な O(N + M) のマッチングを欲しい(ハッシュ衝突を気にしたくない)ときに使う。 パターンの各前缀について「最長の真前缀かつ真後缀」を事前計算する。
失敗関数 · LC 28 · LC 459
Rabin–Karp
複数のパターンを同時に探す、または固定長 k のスライディングウィンドウを扱うときに使う。 ローリング多項式ハッシュが文字比較を数値比較に置き換える;衝突時は文字単位での検証が必要。
ローリングハッシュ · LC 187 · LC 1044
Z アルゴリズム
すべての出現位置 + 文字列の追加性質(最長 border、最長回文前缀)が欲しいときに使う。
P + "#" + T 上の Z 配列が一度に全マッチを与え、 ついでに構造情報も無料で得られる。Z-box · LC 214 · LC 1392