文字列マッチング
01 / 共通の仕組み
テキスト T の中にパターン P を見つける —— 素朴な O(N·M) を 3 つのサブパターンすべてが O(N + M) に落とし込む。 共通の手口はパターンの構造情報を事前計算すること。 不一致のたびに走査が冗長な比較をスキップできるようにする。 違うのは何を事前計算するかだけ:失敗関数(KMP)、ローリングハッシュ(Rabin–Karp)、 連結文字列上の前缀マッチ配列(Z)。
01 / 一文での本質
Z[i] は位置 i から始まり、 S の前綴と一致する最長部分文字列の長さ。パターン + "#" + テキストを連結し、Z[i] = |P| となる i がマッチ位置。 Z-box[L, R]が作業を O(N + M) に償却する。
問題T における P の全マッチP"abc"T"abcxabcabc"
パターン P = "abc"、テキスト T = "abcxabcabc"。手順:S = P + "#" + T を作り、Z[] を計算し、マッチを読み取る。
ステップ
0 / 36
i
—
L / R
—
マッチ
—
0 / 36
02 / パターンの骨格
# Z[i] = i から始まり S の前綴と一致する最長長Z ← [0] * n; L ← 0; R ← 0for i in range(1, n):if i < R:Z[i] ← min(R − i, Z[i − L]) # 箱内のミラー値を流用while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:Z[i] += 1 # 文字単位で右へ伸ばすif i + Z[i] > R:L ← i; R ← i + Z[i] # Z-box を広げる# T 中のマッチ位置 = { i − |P| − 1 : Z[i] == |P| }
03 / このパターンを使うべき合図
「全ての出現位置を求める」
LC 28 のような教科書的トリガー。
S = P + "#" + T を作り、 Z を計算する。Z[i] = |P| かつ i > |P| の位置がすべて T 中の出現。 連結トリックによりパターンマッチが純粋な「前綴自己マッチ」問題になる。「最短回文」
LC 214。
s + "#" + reverse(s) を連結し、i + Z[i] = |S| を満たす最大の Z[i] を読み取る —— これが s の前綴であり同時に reverse(s) の後綴であるもの、 すなわち最長回文前綴。残りを反転して頭に付ければ答え。「longest happy prefix(最長ハッピー前綴)」
LC 1392。真前綴かつ真後綴である最長の前綴。KMP の失敗関数が直球だが、Z でも解ける: Z 配列を走査して
i + Z[i] = n を満たす最大の Z[i] が答えの長さ。「異なる部分文字列の数 / 一般文字列解析」
LC 3008 のような一般文字列解析。あるパターンの各位置における前綴マッチ長を問うものなら、 Z が一回で完全な構造情報を返し、本来の問いはたいてい軽い後処理で済む。
04 / よくある落とし穴
i.
区切り文字を忘れる/誤る。
P + "#" + T の "#" は P にも T にも現れない文字でなければならない。 省くと T 内のマッチが P 側へ伸びて Z[i] が |P| を超え、 多重カウントや見落としが発生する。アルファベット外の番兵を選ぶこと。ii.
Z と KMP の失敗関数を混同する。
別配列で別問題。KMP の
π[i] = P[0..i] の真前綴かつ真後綴の最長長; Z の Z[i] = 位置 i から始まり S の前綴と一致する最長長。 両者ともパターンマッチを解けるが、添字の向きが逆 —— 漸化式を混在させない。iii.
Z-box 更新の off-by-one:正しくは
i + Z[i] > R、≥ R ではない。[L, R] は最右到達の一致窓を保持する;新たな一致が R を厳密に超えたときのみ拡張する。≥ を使うと L だけが i にリセットされ R は伸びず、 償却解析が崩れる(答えは正しいが二次に退化)。05 / LeetCode で練習
4 問。Z が最も簡潔か、KMP と肩を並べる問題群。LC 214 は反転連結の定番トリック; LC 3008 は一般文字列解析の代表例。
— / どれをいつ使うか
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