文字列マッチング
01 / 共通の仕組み
テキスト T の中にパターン P を見つける —— 素朴な O(N·M) を 3 つのサブパターンすべてが O(N + M) に落とし込む。 共通の手口はパターンの構造情報を事前計算すること。 不一致のたびに走査が冗長な比較をスキップできるようにする。 違うのは何を事前計算するかだけ:失敗関数(KMP)、ローリングハッシュ(Rabin–Karp)、 連結文字列上の前缀マッチ配列(Z)。
01 / 一文での本質
文字比較をハッシュ比較に置き換える —— 新しい文字を足し、抜ける文字を引くだけで、各ウィンドウのハッシュを O(1) で更新できる。ハッシュ一致時は衝突を排除するため必ず文字単位で検証する。
問題T 中の P の全出現位置P | Tabc | abcxabcdabc
テキスト長 11、パターン長 3。パターンを 1 度ハッシュし、T の最初のウィンドウもハッシュ、以後はスライドごとに O(1) で更新。
ステップ
0 / 14
ウィンドウ
—
ハッシュ
—
マッチ
—
0 / 14
02 / パターンの骨格
# BASE^(M-1) mod MOD はループ外で一度だけ計算H ← hash(P); h ← hash(T[0..M-1])powM ← BASE^(M-1) mod MODfor i in 0..N-M:if h == H and T[i..i+M-1] == P:record(i) # 検証で衝突を排除if i < N-M:h ← ((h − T[i]*powM) * BASE + T[i+M]) mod MOD# 期待 O(N + M);検証はハッシュ一致時のみ
03 / このパターンを使うべき合図
「テキスト中の全ての出現位置を求める」
教科書的なトリガー。LC 28 の「最初の出現位置を返す」はすべての出現位置に拡張できる。 KMP、Z、Rabin–Karp のいずれでも解けるが、最悪線形が必須でないなら Rabin–Karp が最も書きやすい。
「最長の重複部分文字列」
LC 1044。答えの長さ L を二分探索し、内部でローリングハッシュを使って長さ L の重複ウィンドウが存在するかを O(N) で判定する。全体は O(N log N) —— ローリングハッシュが内側を平方から線形に落とす肝。
「繰り返し DNA 配列」
LC 187 —— 固定ウィンドウ
k = 10。ローリングハッシュで一度走査し、 ハッシュ値もしくは部分文字列で重複除去する。各シフトは数値 1 つの更新だけで、 10 文字を毎回読み直す必要はない。「複数パターンを同時に探索」
多パターンマッチングの定石は Aho–Corasick だが、マルチ Rabin–Karp は導入として簡単: 同じ長さのパターンを全部ハッシュ化して集合に入れ、テキストを 1 回走査して各ウィンドウで集合検索。 ヒット時は文字単位の検証で誤検出を弾く。
04 / よくある落とし穴
i.
ハッシュ一致時に検証をスキップする。
ハッシュの一致は必要条件であって十分条件ではない。 異なるウィンドウが
MOD で同じ剰余に落ちることはある。 一致を証拠扱いすると偽マッチを返す。h == H のときは必ずウィンドウとパターンを文字単位で比較する; 真の衝突は稀なので、検証コストは償却で消える。ii.
単一かつ小さい、あるいは知られた MOD を使う。
固定で小さい MOD は攻撃される —— 敵対的入力ではすべてのウィンドウが衝突して、 O(N) が O(NM) まで悪化する。対処:109 程度の大きな素数とランダム化基を使う、 あるいはさらにダブルハッシュ —— 独立な (BASE, MOD) 2 組を持ち、両方一致時のみ検証する。
iii.
BASE^(M-1) mod MOD の事前計算を忘れる。ローリング更新では抜ける文字の寄与を引くために
powM = BASE^(M-1) mod MOD が必要。 これをループ内で計算すると 1 シフトあたり O(log M) かかり、線形時間の保証が静かに壊れる。 走査前に 1 回計算しておき、以後はそれを使い回す。05 / LeetCode で練習
4 問、おおよそ難易度順。LC 1044 はローリングハッシュの本領発揮 —— 答えの長さに二分探索を効かせられるのはこの手法だけ。KMP/Z では逆に苦しい。
— / どれをいつ使うか
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