一、要解决的问题
给你 m 个模式串（如若干敏感词）和一个大文本 T，问每个模式串在 T 中出现了几次（或是否出现）。模式串总长可达 106，对每个模式串单独跑 KMP 是 O(m·|T|)，会超时。AC 自动机可以只扫一遍文本，同时匹配所有模式串。
生活类比：查词典时你不可能每查一个词就从第一页翻起。你会顺着拼音索引往下走；发现当前词查不到时，不是回到封面，而是跳到"前缀最接近的条目"继续。Trie 树就是索引，fail 指针就是那张"跳到哪继续"的字条。
二、预备：KMP 的 next 数组讲了什么
单模式匹配时，若文本与模式在位置 j 失配，朴素做法回退到起点重比。KMP 发现：模式串自身的最长公共前后缀（next 数组）告诉我们"已经匹配的部分里，有多长可以复用"，于是模式串只需向右滑动，文本指针永不回退。
next[j] = 模式串前缀 p[1..j] 的最长真前缀 = 真后缀 的长度（失配后的退路）
AC 自动机就是把 next 数组从一维的"链"推广到 Trie 树上的每个节点——这个推广后的 next 就叫 fail 指针。
三、结构：Trie + fail 指针
零基础提示 · Trie 是什么：Trie（字典树）把一堆字符串的公共前缀合并成一棵树：从根出发，每条边写一个字符，从根到某节点的路径就是一个前缀。比如 "she"、"he" 都含 "he"，但前缀不同所以挂在不同分支；而 "she" 与 "shy" 会共享 "sh" 这段路径。插入一个字符串 = 从根沿路走，没路就新建节点。
- 建 Trie：把所有模式串插进一棵字典树，每个模式串的末端节点打上 end 标记（并记录是哪个模式串）。
- BFS 建 fail：节点 u 的 fail 指向"root 出发能走到的、与 root→u 路径串的最长真后缀对应的节点"。按层 BFS，因为 u 的 fail 一定比 u 浅，可以在处理 u 之前算好。
- 匹配：文本指针在 Trie 上走，走不动就沿 fail 跳，直到能走或回到 root。每到一个节点，它（及其 fail 链上的 end 节点）都对应若干次模式串出现。
四、出现次数统计：fail 树与子树和
文本扫描时若停在节点 u，那么 u 及 u 的整条 fail 链上的 end 节点都各出现一次。逐个跳 fail 统计会被 aaaa… 型数据卡成 O(n²)，正确做法是：
- 扫描文本时，每到达节点 u 就
cnt[u]++（只打点，不统计）。 - 把 fail 指针全部反过来看：fail 构成一棵以 root 为根的 fail 树，u 的 fail 链恰好是 u 到根的路径。
- "u 的出现要累加到 fail 链上每个祖先" ⇔ "fail 树上子树和"：按 BFS 序逆序把 cnt[u] 累加到 cnt[fail[u]]。
- 最后，第 i 个模式串末端节点的 cnt 就是它的出现次数。
模式串出现次数 = 其末端节点在 fail 树上的子树和（cnt 逆 BFS 序累加）
匹配走查：文本 "ushers"，模式串 {he, she}
| 读到字符 | 自动机走到 | 动作 |
|---|---|---|
| u | root | 没有 u 开头的模式串，原地不动 |
| s | s | 进入 Trie |
| h | sh | 继续深入 |
| e | she★ | 命中模式串 she，cnt[she]++（同时 fail 链上的 he 稍后会通过子树和得到这次出现） |
| r | root | "she" 没有 r 边，沿压缩转移（经 fail）回退到 root |
| s | s | 重新进入 Trie；扫描结束，逆 BFS 序累加子树和，输出答案 |
五、模板代码（骨架）
// 建 fail（BFS）
queue<int> q;
for (int c = 0; c < 26; c++) if (ch[0][c]) q.push(ch[0][c]); // root 的儿子 fail=0
while (!q.empty()) {
int u = q.front(); q.pop();
for (int c = 0; c < 26; c++) {
int v = ch[u][c];
if (v) { fail[v] = ch[fail[u]][c]; q.push(v); }
else ch[u][c] = ch[fail[u]][c]; // 顺便补全转移（图化）
}
}
// 扫描文本打标记
for (int i = 0, u = 0; t[i]; i++) { u = ch[u][t[i]-'a']; cnt[u]++; }
// 逆 BFS 序做 fail 树子树和
for (int i = bfsOrder.size()-1; i >= 0; i--) cnt[fail[bfsOrder[i]]] += cnt[bfsOrder[i]];六、易错点清单
- 节点数 = 模式串总长 + 1，数组别开小；多组数据要清空（trie 数组、end、cnt）。
- 多个相同模式串要分别计数时，end 记列表或出现次数，不能只存一个编号（P3796 的"重复答案按输入序输出"）。
- 逆 BFS 序累加的顺序不能反：必须从深到浅。
- 文本长度 × 节点数的复杂度错觉：匹配是 O(|T| + 模式串总长)，与模式串个数无关。
七、练习
- P5357【模板】AC 自动机（二次加强版）——必须用 fail 树子树和，暴力跳 fail 会 TLE
- P3796 AC 自动机（简单版 II）——统计出现次数最多的模式串
- 真题对照：CSP-S 2025 T3 谐音替换（ACAM + fail 树满分做法）