字符串匹配
01 / 共享的机制
在文本 T 中找模式 P —— 朴素法是 O(N·M),这三个子模式都把它压到 O(N + M)。 它们的共同套路是预处理模式串的结构信息,让扫描在每次失配时都能跳过冗余比较; 区别只在预处理什么:失败函数(KMP)、滚动哈希(Rabin-Karp),或者拼接串上的前缀匹配数组(Z)。
01 / 一句话本质
把字符比较换成哈希比较 —— 每滑动一格,只加进新字符、减去离开字符,就能在 O(1)内更新窗口哈希。哈希命中后必须逐字符复核以排除碰撞。
题目找出 P 在 T 中的全部出现位置P | Tabc | abcxabcdabc
文本长度 11,模式长度 3。先把模式哈希一次,再哈希 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 二分,内层用滚动哈希在 O(N) 内检测是否存在长度 L 的重复窗口。总复杂度 O(N log N) —— 滚动哈希是让内层从平方降到线性的关键。
"重复 DNA 序列"
LC 187 —— 固定窗口
k = 10。滚动哈希扫一遍后用哈希值或子串本身去重; 每次滑动只更新一个数字,而不是重新读 10 个字符。"同时匹配多个模式"
Aho–Corasick 是多模式匹配的教科书答案,但多模式 Rabin–Karp 是更易上手的入口: 把所有等长模式的哈希丢进一个集合,扫文本时每个窗口查一次集合,命中再逐字符复核以排除误报。
04 / 常见坑
i.
哈希命中时没复核。
哈希相等是必要条件,不是充分条件。两个不同窗口完全可能 mod
MOD 后相等。要是把哈希相等当证据,就会报出假匹配。h == H 时必须逐字符比较一次窗口和模式;摊销下来开销可以忽略,因为真正的碰撞很罕见。ii.
用单个、过小、或大家都在用的 MOD。
小的、固定的 MOD 容易被针对 —— 对手能构造让每个窗口都碰撞的输入, 把 O(N) 拖成 O(NM)。修法:取 109 量级的大质数 + 随机化基, 或者更进一步采用双哈希 —— 两组独立 (BASE, MOD),两者都相等才进入复核。
iii.
忘了预计算
BASE^(M-1) mod MOD。滚动一步需要
powM = BASE^(M-1) mod MOD 来减去离开字符的贡献。 要是放进循环里算,每次滑动都要 O(log M),默默把线性复杂度毁掉。 扫描前算一次,后面直接复用即可。05 / 去 LeetCode 上练习
四道题,大致按难度排序。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