引言在字符串处理中最经典的问题莫过于模式匹配给定一个文本串和一个模式串找出模式串在文本串中的所有出现位置。最朴素的做法是暴力匹配——每次失配后模式串整体后移一位重新开始比较。这个方法在最坏情况下的复杂度是 O(n×m)当字符串长度达到 10⁵ 甚至 10⁶ 时根本无法接受。KMP 算法Knuth-Morris-Pratt的诞生彻底改变了这一局面。它通过预处理模式串构建一个next 数组或称前缀函数在失配时能够“跳着走”而不是笨拙地一步一挪从而将匹配复杂度降为 O(nm)。但 KMP 只能处理单个模式串的匹配问题。如果同时有多个模式串需要匹配呢比如在一段文本中查找若干个敏感词AC 自动机Aho-Corasick Automaton正是为此而生。它将 KMP 的失配指针思想从线性结构推广到了Trie 树上实现了一次扫描文本、同时匹配所有模式串的强大功能。如果说暴力匹配是“走一步看一步”那么 KMP 就是“跳着走”——它记住了模式串自身的结构失配时直接跳到下一个可能匹配的位置。而 AC 自动机则是“在树上跳着走”——它把多个模式串组织成一棵树失配时沿着树上的“捷径”跳跃一次扫描就能命中所有目标。前置知识在学习 KMP 和 AC 自动机之前你需要掌握以下基础字符串的基本概念前缀、后缀、子串、真前缀/真后缀。Trie 树字典树一种用于高效存储和查找字符串集合的树形数据结构。AC 自动机建立在 Trie 树之上。队列BFSAC 自动机构建 fail 指针时使用广度优先搜索。递归与DFS理解 fail 树和在 AC 自动机上做 DP 时需要。第一章KMP算法——单模式匹配的“跳跃者”1.1 从暴力到KMP为什么要“跳”考虑文本串s aaaaaaaaab模式串p aaaab。暴力匹配时每次在最后一个字符b处失配后模式串只能整体后移一位然后从模式串的第一个字符重新开始比较。这导致大量重复比较——明明前面四个a已经匹配过了为什么不能利用这个信息KMP 的核心洞察是失配时模式串不需要从头开始。如果模式串的某个前缀和已经匹配的文本后缀相同那么模式串可以直接滑动到这个位置继续比较。1.2 next 数组的定义next[i]或称pi[i]表示模式串p[0...i-1]的最长公共真前后缀的长度。换句话说它是p的前i个字符组成的子串中既是前缀又是后缀的最长长度且长度小于i。例如p ababanext[0] -1约定next[1] 0a 没有真前后缀next[2] 0ab 没有next[3] 1aba 的前缀 a 后缀 anext[4] 2abab 的前缀 ab 后缀 abnext[5] 3ababa 的前缀 aba 后缀 aba1.3 如何求解 next 数组求解 next 数组的过程本质上是模式串与自身进行匹配。设j表示当前已匹配的前缀长度初始j 0。从i 2开始遍历模式串假设下标从 1 开始for (int i 2; i m; i) { while (j p[i] ! p[j 1]) j nxt[j]; if (p[i] p[j 1]) j; nxt[i] j; }递推逻辑已知next[j] k表示p[0...k-1] p[j-k...j-1]。求next[j1]时只需比较p[k]与p[j]若相等则next[j1] k 1。若不相等则令k next[k]继续比较递归地寻找更短的相同前后缀。1.4 KMP 匹配过程有了 next 数组匹配就变得简单了for (int i 1; i n; i) { while (j s[i] ! p[j 1]) j nxt[j]; if (s[i] p[j 1]) j; if (j m) { // 匹配成功位置为 i - m 1 j nxt[j]; // 继续寻找下一个匹配 } }复杂度构建 next 数组 O(m)匹配过程 O(n)总复杂度 O(nm)。第二章AC自动机——多模式匹配的“树上游侠”2.1 从KMP到AC自动机KMP 解决了一个模式串的匹配问题。但如果模式串有多个比如敏感词列表对每个模式串分别跑一次 KMP复杂度为 O(n × k)其中 k 是模式串数量显然不可行。AC 自动机的思路是把所有模式串插入到一棵 Trie 树中然后在树上做 KMP。如果说 KMP 的 next 数组是在一条线上“跳”那么 AC 自动机的 fail 指针就是在树上“跳”——从当前节点跳到另一个节点使得跳转后的字符串是当前匹配串的最长后缀。2.2 构建 Trie 树首先将所有模式串插入到一棵 Trie 树中int tr[N][26], tot; void insert(string s) { int u 0; for (char c : s) { int v c - a; if (!tr[u][v]) tr[u][v] tot; u tr[u][v]; } cnt[u]; // 标记该节点是一个模式串的结尾 }2.3 fail 指针的定义在 KMP 中next[j]表示失配后模式串应该跳到的位置。在 AC 自动机中fail 指针扮演了相同的角色fail[u]指向Trie 中存在的最长的、是 u 所代表字符串的真后缀的那个节点。例如模式串集合为{he, she, his, hers}节点she的 fail 指针指向he因为he是she的最长后缀且出现在 Trie 中。重要性质所有 fail 指针构成一棵树称为fail 树。这棵树在后来的许多应用中非常关键。2.4 如何求解 fail 指针求解 fail 指针使用BFS广度优先搜索void build() { queueint q; // 初始化根节点(0)的所有非空子节点的 fail 指向根 for (int i 0; i 26; i) { if (tr[0][i]) { fail[tr[0][i]] 0; q.push(tr[0][i]); } } while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i 26; i) { int v tr[u][i]; if (v) { // 核心v 的 fail 指向 u 的 fail 的 i 儿子 fail[v] tr[fail[u]][i]; q.push(v); } else { // 优化将不存在的转移直接指向 fail 的对应转移 tr[u][i] tr[fail[u]][i]; } } } }理解这段代码对于节点u的字符i儿子vv的 fail 指针应该指向fail[u]的i儿子。这相当于在 Trie 树上“递归地”寻找最长后缀。如果u没有字符i的儿子我们直接把tr[u][i]设置为tr[fail[u]][i]。这一步称为“补全转移”它让 AC 自动机变成了一个完整的DFA确定性有限自动机——无论输入什么字符从任何状态出发都一定有转移。2.5 多模式匹配匹配时只需在补全后的自动机上走一遍文本串int query(string s) { int u 0, ans 0; for (char c : s) { int v c - a; u tr[u][v]; // 直接转移已被补全 // 统计所有以当前匹配后缀结尾的模式串 for (int t u; t cnt[t] ! -1; t fail[t]) { ans cnt[t]; cnt[t] -1; // 防止重复计数 } } return ans; }复杂度建 Trie O(Σ|模式串|)建 fail O(Σ|模式串| × 字符集大小)匹配 O(|文本串| 匹配次数)。第三章fail树——失配指针的“家族谱系”3.1 什么是 fail 树所有节点的 fail 指针构成一棵以根节点为根的树。在这棵树中每个节点的父节点就是它的 fail 指针指向的节点。如果把 AC 自动机的节点看作“状态”那么 fail 树描述的是状态之间的“后缀包含关系”——u的 fail 链上的所有节点都是u所代表字符串的后缀。3.2 fail 树的应用fail 树将 AC 自动机的问题转化为了树上问题可以用树链剖分、树上差分、DFS 序等技巧来解决。典型应用统计每个模式串在文本串中出现的次数。朴素做法是每匹配到一个节点u就暴力跳 fail 链统计答案。但这样最坏复杂度是 O(n × 树高)可能退化到 O(n²)。优化方法匹配时只在每个到达的节点u上打一个标记1。匹配结束后在 fail 树上做子树求和——节点u的答案等于其 fail 子树中所有标记的和。这是因为如果某个节点v被标记了那么所有 fail 树上v的祖先即v的后缀都应该被统计到。3.3 例题洛谷 P5357 【模板】AC自动机二次加强版这道题要求统计每个模式串在文本串中出现的次数。正解就是建 AC 自动机匹配时打标记最后在 fail 树上 DFS 做子树求和。第四章在AC自动机上做DPAC 自动机不仅是一个匹配工具还可以作为DP 的状态图来使用。这是许多难题的突破口。4.1 核心思想把 AC 自动机的每个节点看作一个 DP 状态表示“当前已经匹配到自动机上的哪个节点”。在自动机上每走一步读入一个字符就转移到下一个状态。同时某些状态可能是“危险状态”即匹配到了某个模式串在 DP 中需要避免或特殊处理。4.2 典型模型模型一不包含任何模式串的字符串计数给定若干个模式串求长度为 L 的、不包含任何模式串作为子串的字符串数量。解法建 AC 自动机标记所有模式串的结尾节点及其 fail 树上的所有祖先为“危险节点”。设dp[i][u]表示长度为 i、当前在节点 u 的合法字符串数量。转移dp[i1][tr[u][c]] dp[i][u]要求tr[u][c]不是危险节点。最终答案Σ dp[L][u]所有非危险节点。模型二包含至少一个模式串的期望/计数通常用容斥或矩阵快速幂当 L 很大时处理。第五章例题与详细解析例题1KMP模板 —— 洛谷 P3375题目描述给定两个字符串s1文本串和s2模式串求出s2在s1中所有出现的位置并输出s2的每个前缀的最长 border 长度。解题思路这是 KMP 的纯模板题。需要实现两个功能计算s2的 next 数组即每个前缀的最长 border 长度。用 KMP 在s1中匹配s2记录所有匹配位置。代码实现#include bits/stdc.h using namespace std; const int N 1e6 5; int nxt[N], n, m; int main() { string s, p; cin s p; n s.size(), m p.size(); s s, p p; // 下标从1开始 // 求 next 数组 for (int i 2, j 0; i m; i) { while (j p[i] ! p[j 1]) j nxt[j]; if (p[i] p[j 1]) j; nxt[i] j; } // KMP 匹配 for (int i 1, j 0; i n; i) { while (j s[i] ! p[j 1]) j nxt[j]; if (s[i] p[j 1]) j; if (j m) { cout i - m 1 \n; // 匹配位置 j nxt[j]; } } // 输出 next 数组 for (int i 1; i m; i) cout nxt[i] ; return 0; }解析下标从 1 开始是为了方便处理边界。nxt[1] 0是默认的循环从i 2开始。匹配成功后将j回退到nxt[j]以便寻找下一个重叠匹配。例题2AC自动机模板 —— 洛谷 P3808题目描述给定 n 个模式串和一个文本串问有多少个模式串在文本串中出现过。解题思路这是 AC 自动机的最基础应用。建 Trie 树构建 fail 指针然后在文本串上跑匹配统计有多少个模式串被匹配到。注意事项本题数据中有重复的模式串重复的单词应该计算多次。但题目问的是“有多少个模式串出现过”所以重复的只需要统计一次即可。匹配时访问过的节点要标记避免重复计数。代码实现核心部分struct Node { int ch[26], fail, cnt; } tr[N]; void insert(string s) { int u 0; for (char c : s) { int v c - a; if (!tr[u].ch[v]) tr[u].ch[v] tot; u tr[u].ch[v]; } tr[u].cnt; // 可能有重复模式串用 cnt 计数 } void build() { queueint q; for (int i 0; i 26; i) { if (tr[0].ch[i]) { tr[tr[0].ch[i]].fail 0; q.push(tr[0].ch[i]); } } while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i 26; i) { int v tr[u].ch[i]; if (v) { tr[v].fail tr[tr[u].fail].ch[i]; q.push(v); } else { tr[u].ch[i] tr[tr[u].fail].ch[i]; } } } } int query(string s) { int u 0, ans 0; for (char c : s) { u tr[u].ch[c - a]; for (int t u; t tr[t].cnt ! -1; t tr[t].fail) { ans tr[t].cnt; tr[t].cnt -1; // 标记已访问 } } return ans; }解析build()中处理tr[u].ch[i] tr[tr[u].fail].ch[i]完成了自动机的“补全”。query()中暴力跳 fail 链是可行的因为每个节点最多被访问一次cnt被设为 -1 后不再访问。例题3病毒 —— 洛谷 P2444题目描述给定若干个 01 字符串作为“病毒代码”问是否存在一个无限长的 01 字符串使得其中不包含任何一段病毒代码。解题思路这是一道 AC 自动机的思维变形题。关键在于将问题转化为图论中的环检测问题。步骤建 AC 自动机将所有病毒代码插入 Trie 树构建 fail 指针。标记危险节点一个节点是“危险”的当且仅当它本身是某个病毒代码的结尾节点或它的 fail 链上有危险节点。这是因为如果当前匹配到的字符串的后缀是病毒代码那么这个字符串本身就包含了病毒。找环在 AC 自动机上从根节点出发沿着非危险节点的转移边走看是否能形成一个环。如果能形成环说明可以在这个环上无限循环构造出无限长的安全代码。如果不能说明所有路径最终都会走到危险节点不存在无限长的安全代码。代码实现核心const int MAXN 30005; int ch[MAXN][2], fail[MAXN], tot; bool danger[MAXN], vis[MAXN], ins[MAXN]; void insert(string s) { int u 0; for (char c : s) { int v c - 0; if (!ch[u][v]) ch[u][v] tot; u ch[u][v]; } danger[u] true; } void build() { queueint q; for (int i 0; i 2; i) { if (ch[0][i]) q.push(ch[0][i]); } while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i 2; i) { if (ch[u][i]) { fail[ch[u][i]] ch[fail[u]][i]; danger[ch[u][i]] | danger[fail[ch[u][i]]]; // 传递危险标记 q.push(ch[u][i]); } else { ch[u][i] ch[fail[u]][i]; } } } } // DFS 找环 bool dfs(int u) { ins[u] true; for (int i 0; i 2; i) { int v ch[u][i]; if (danger[v]) continue; if (ins[v]) return true; // 找到环 if (!vis[v]) { vis[v] true; if (dfs(v)) return true; } } ins[u] false; return false; }解析危险标记需要通过 fail 链传递。找环时用ins数组记录当前 DFS 栈中的节点检测到重复访问即说明有环。根节点0是安全的起始点。第六章拓展与应用6.1 拓扑排序优化匹配统计在需要统计每个模式串出现次数的题目中如 P5357暴力跳 fail 链可能超时。优化方法是匹配时只在节点上打标记。按 fail 树的拓扑序即 BFS 序的逆序从叶子向上累加标记。6.2 AC自动机 矩阵快速幂当需要统计长度为 L 的不包含任何模式串的字符串数量且 L 很大如 10⁹时可以将 AC 自动机的转移图写成邻接矩阵然后用矩阵快速幂加速 DP。6.3 可持久化AC自动机支持在 Trie 树上进行持久化操作实现可回溯的字符串匹配。6.4 与后缀自动机SAM的对比AC 自动机处理多个模式串在一个文本串中的匹配基于 Trie fail。后缀自动机处理一个模式串在多个文本串中的匹配或处理一个字符串的所有子串信息。两者各有侧重互为补充。总结KMP 和 AC 自动机是字符串匹配领域的两座里程碑。KMP 用 next 数组实现了单模式串的线性匹配而 AC 自动机将其思想推广到 Trie 树上实现了多模式串的同时匹配。学习它们的要点理解 next/fail 的本质它们记录的是“失配后往哪跳”本质是最长公共前后缀的信息。掌握 BFS 构建 fail 的过程这是 AC 自动机的核心理解了它就等于理解了 AC 自动机。认识 fail 树它将 AC 自动机的问题转化为树上问题是许多高级应用的基础。灵活运用自动机上的 DPAC 自动机是一个天然的 DFA可以在上面进行各种 DP。