字符串匹配
01 / 共享的机制
在文本 T 中找模式 P —— 朴素法是 O(N·M),这三个子模式都把它压到 O(N + M)。 它们的共同套路是预处理模式串的结构信息,让扫描在每次失配时都能跳过冗余比较; 区别只在预处理什么:失败函数(KMP)、滚动哈希(Rabin-Karp),或者拼接串上的前缀匹配数组(Z)。
01 / 一句话本质
失败函数告诉你模式串已经有多少字符与后缀匹配 —— 于是失配时直接跳到那个位置,而不是从头比较。模式预处理一次、文本扫一次,两边都是线性的。
题目找出 P 在 T 中的所有出现位置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[] 扫文本 Tj ← 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 时,必须先令 j ← fail[j−1] 再递增 i, 否则会漏掉重叠匹配。模式 "aaa" 在文本 "aaaaa" 中有三处匹配,不是一处。iii.
把「前缀函数」和「next 数组」搞混。
两种教学惯例:前缀函数
fail[i] 给出以 i 结尾的前缀的 LPS 长度;经典的 next[i] 给出长度为 i 的前缀的 LPS(整体位移一格), 有的教材在 0 处存 −1。同一个算法,不同的下标 —— 选一种贯彻到底,尤其是从别处粘贴代码时。05 / 去 LeetCode 上练习
四道题。第一题是教科书式用法;后三题都是同一个失败函数的「换皮」应用 —— 周期检测、回文构造、以及 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