算法设计第 9 章：子串——KMP、AC 自动机与后缀数组构造
串匹配是算法课里少见的"工程与理论完全重合"的一章：编辑器查找、日志过滤、基因序列比对、拼写纠错，背后都是这几个结构。它的难点不在代码量，而在复杂度里那几个符号的来历——为什么 KMP 是 O(n+m) 而不是 O(nm)，为什么 AC 自动机建自动机是 O(m|Σ|) 而匹配是 O(n)，为什么后缀数组倍增是 O(n log²n) 而线性构造能做到 O(n)。这一章的核心是把每个复杂度拆到具体的那一层循环上。
一、单模式与多模式匹配
单模式匹配：给定文本 T（长度 n）与模式 P（长度 m），找出 P 在 T 中所有出现位置。 多模式匹配：给定一组模式 {P₁, …, Pₖ} 与文本 T，一次扫描找出所有模式的所有出现。
| 方法 | 预处理 | 匹配 | 适用 |
|---|---|---|---|
| 朴素（暴力） | 无 | O(nm) | 教学、极短模式 |
| KMP | O(m) | O(n) | 单模式，在线 |
| Rabin-Karp | O(m) | 期望 O(n+m) | 单模式，可哈希 |
| AC 自动机 | O(Σ|Pᵢ|·|Σ|) | O(n + 出现次数) | 多模式 |
| 后缀数组 | O(n log n) | O(m log n) 单次查询 | 静态文本、多次查询 |
朴素算法的瓶颈在于失配后回退文本指针：T 的每个位置都可能被比较 m 次，最坏 O(nm)（如 T = aaaa…a，P = aaab）。
二、KMP 与 AC 自动机
KMP 的核心是 next 数组（失效函数）：next[j] 表示 P[1..j] 的最长真前缀同时也是其后缀的长度。失配时文本指针不回退，模式右移到 next[j] 继续比较——它跳过的是"已知不可能匹配"的位置。预处理 O(m)，匹配 O(n)，总计 O(n+m)。
next 本身用递推求：设已知 next[j] = k，比较 P[j+1] 与 P[k+1]，相等则 next[j+1] = k+1；不等则令 k = next[k] 继续回退，直到相等或 k = 0。这个"回退再回退"的过程总代价是 O(m)，因为 k 每轮最多加 1，回退次数不超过累加的加一次数——这是 KMP 预处理线性的摊还论证，也是最容易讲漏的一步。
void get_next(char *P, int m, int *nxt) {
int j = 0, k = -1; nxt[0] = -1; /* 0 号位哨兵 */
while (j < m) {
if (k == -1 || P[j] == P[k]) { ++j; ++k; nxt[j] = k; }
else k = nxt[k]; /* 回退，文本指针不动 */
}
}
KMP 的匹配过程与求 next 完全同构，只是把"模式自我比较"换成"模式与文本比较"。看懂一个，另一个就免费。
AC 自动机 = Trie + 失配指针。
- 把所有模式插入 Trie，结点记录"是否为某个模式的结尾"。
- BFS 构造 fail 指针：根的儿子 fail 指向根；对结点 u 的字符 c 儿子 v，沿 u 的 fail 链上找第一个有 c 儿子的结点，把 v 的 fail 指向那个儿子；找不到则指向根。BFS 保证按深度递增处理，父亲的 fail 已算好。
- 匹配时文本指针沿 Trie 走，走不通就跳 fail，沿途收集输出（沿 fail 链上报，或用输出链优化避免重复遍历）。
复杂度要分开算：建 Trie 是 O(m)；BFS 填转移表时每个结点要开 |Σ| 个槽，构建合计 O(m|Σ|)，空间同阶；匹配 O(n + z)，z 为出现次数，最坏不超过 O(n + m)。课程里常把三项并记为 O(n + m + |Σ|) 这一量级——|Σ| 这一项不能省：在 Unicode 这类大字符集上，转移表的初始化就是实际瓶颈，改用哈希或平衡树存边可把构建降到 O(m log|Σ|)。
AC 自动机的 fail 指针与 KMP 的 next 本质相同：都是"最长真后缀"，只是一个在单串上、一个在 Trie 上。理解了这一点，两者就不必分别背。
三、后缀数组的倍增构造
后缀数组 sa：把串 S 的 n 个后缀按字典序排序，sa[i] 是排名第 i 的后缀的起始位置；rank[i] 是后缀 i 的排名，二者互为逆置换（rank[sa[i]] = i）。
倍增法：先按首字符排出长度 1 的 rank，再假设已知长度 k 的 rank，用二元组
(rank[i], rank[i + k])
排序得到长度 2k 的 rank。因为比较两个长度 2k 的串等价于比较它的前后两个长度 k 的块，每轮规模翻倍，共 log n 轮。
- 用比较排序：每轮 O(n log n)，总计 O(n log² n)。
- 用基数排序（rank 值域是 0..n，两趟计数排序）：每轮 O(n)，总计 O(n log n)。
- 若 rank 已全不相同可提前终止，实际远快于理论上界。
for (int k = 1; k < n; k <<= 1) {
/* 以 (rank[i], rank[i+k]) 为关键字做基数排序 */
sort_by_second_key(); sort_by_first_key();
/* 重算 rank：二元组不同则排名 +1 */
}
倍增法的常数小、实现短，是工程默认选择；它的代价是 O(log n) 的因子。
四、后缀数组的线性时间构造
要做到 O(n)，必须避免"每轮重排全部后缀"。SA-IS（诱导排序）与 DC3（Skew） 是两条主流路线，都用分治 + 诱导：
- DC3：把后缀按起始下标模 3 分成三组，先递归处理模 3 不为 0 的两组（规模 2n/3），得到它们的相对顺序；再用这次序诱导出模 3 为 0 的那一组的排名；最后归并三组。递归式 T(n) = T(2n/3) + O(n)，解得 O(n)。
- SA-IS：区分 S 型与 L 型后缀，先递归排序 LMS 子串，再诱导出全部后缀。同样 O(n)，常数更小。
线性构造的价值在于大规模文本索引（基因组、日志库）。代价是实现复杂度陡增，几百行且边界条件极多——除非 n 大到 log n 因子不可接受，工程上仍用倍增。
后缀数组本身只是"排好序的后缀起点"，真正让它好用起来的是 LCP 数组（height）：height[i] = LCP(sa[i−1], sa[i])，即相邻两个后缀的最长公共前缀长度。它有 O(n) 的 Kasai 求法（利用 height[i] ≥ height[i−1] − 1 的性质），而任意两个后缀的 LCP 等于它们在 height 上的区间最小值——一次 RMQ 预处理后 O(1) 查询。"排序 + LCP + RMQ"三件套，等价于后缀树的全部功能，却只需几个数组，这是后缀数组取代后缀树的现实原因。
五、编辑距离与最长公共子序列
编辑距离：把串 A（长 m）变成串 B（长 n），允许插入、删除、替换，求最少操作数。
dp[i][j] = min( dp[i-1][j] + 1, /* 删除 A[i] */
dp[i][j-1] + 1, /* 插入 B[j] */
dp[i-1][j-1] + (A[i] != B[j]) ) /* 替换或匹配 */
基例 dp[i][0] = i、dp[0][j] = j。时间 O(mn)，空间 O(mn)（可滚动到 O(min(m,n))）。
最长公共子序列（LCS）：
dp[i][j] = dp[i-1][j-1] + 1 , A[i] == B[j]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) , A[i] != B[j]
时间 O(mn)，空间可滚动到 O(min(m,n))，但要输出具体子序列就必须保留整张表（或改用 Hirschberg 分治，O(min(m,n)) 空间、O(mn) 时间）。
两者的关系值得记：编辑距离只允许插入删除时，编辑距离 = m + n − 2·|LCS|。这条恒等式把两个 DP 连成一体。
工程上还有两个常见变体：把替换代价设为 2（等价于"删一个再插一个"）时，编辑距离直接退化成上式的形式；生物序列比对用仿射代价（开一个空位罚得重、延长空位罚得轻），此时状态必须增加一维表示"当前是否处在空位中"，时间仍是 O(mn)，空间从两行变三行。代价模型一变，状态就要升维——这是第 3 章"状态设计三问"的直接应用。
易错点
- KMP 失配时同时回退文本指针，退化成 O(nm)。
- AC 自动机构造 fail 时用 DFS 而非 BFS，父亲的 fail 还没算好。
- 后缀数组倍增时忘记在串尾加一个小于所有字符的哨兵，导致短后缀排序错。
- 认为倍增法就是 O(n log n)，忽略比较排序带来的第二个 log。
- LCS 想用滚动数组还原具体序列，信息不足。
这一章在整门课里的位置
本章是第 3 章动态规划的直接应用（编辑距离、LCS 都是二维 DP），也是第 2 章分治的延伸（DC3 的递归式 T(n) = T(2n/3) + O(n)）。第 7 章的 Rabin-Karp 指纹是蒙特卡洛思想在字符串上的落地；本章的后缀结构又常作为第 10 章优化的载体——用后缀数组把 O(n²) 的子串比较降到 O(n log n)。
本文是《算法设计与分析（89 讲）》第 9 章的知识点摘要。完整板书与代码见 课程页；上一章 NP 完全性理论，下一章 算法优化。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 算法设计与分析（89讲） 89 讲