字符串匹配
01 / 共享的机制
在文本 T 中找模式 P —— 朴素法是 O(N·M),这三个子模式都把它压到 O(N + M)。 它们的共同套路是预处理模式串的结构信息,让扫描在每次失配时都能跳过冗余比较; 区别只在预处理什么:失败函数(KMP)、滚动哈希(Rabin-Karp),或者拼接串上的前缀匹配数组(Z)。
01 / 一句话本质
Z[i] 是从位置 i 开始、 与 S 的前缀匹配的最长子串长度。把模式 + "#" + 文本拼起来, 凡是 Z[i] = |P| 的位置就是一次匹配。 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) 拼起来,找最大的 Z[i] 使 i + Z[i] = |S| —— 就是 s 的最长「同时也是 reverse(s) 后缀」的前缀, 即最长回文前缀。剩下那段反过来贴到最前面就行。"最长 happy 前缀"
LC 1392。最长既是真前缀又是真后缀。KMP 的失败函数最直接,但 Z 也搞得定: 扫一遍 Z 数组,找最大的
Z[i] 满足 i + Z[i] = n,该值即答案长度。"统计不同子串 / 一般字符串分析"
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 上练习
四道题,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