AC 自动机（Aho-Corasick）
字符串 · 多模式匹配 · Trie + fail · O(n + m + z)
一次找出一大堆模式
前面的 KMP、Rabin-Karp、Boyer-Moore 都是单模式匹配——一次找一个模式。如果要在文本里同时找 一组模式（比如敏感词过滤、多关键词高亮），挨个跑一遍太慢。AC 自动机（Aho-Corasick）把这组模式一次性编译成一台自动机，然后一趟扫过文本，就能报出所有出现（含重叠），复杂度 O(文本长 + 模式总长 + 命中数)。
Trie + fail 指针
第一步：把所有模式塞进一棵 字典树 Trie，共享前缀（he 和 hers 共用 h→e）。第二步：给每个状态建一条 fail 指针——它正是 KMP 里部分匹配表 π 的多模式推广：fail[u] 指向「u 代表的串的最长真后缀，且该后缀也是 Trie 中的一条路径」。匹配失配时不必回退文本，顺着 fail 指针跳到这个「次好」的状态继续。
fail 用 BFS 逐层构造（父的 fail 先算好才能算子的）：状态 u 沿边字符 c 的孩子 v，其 fail[v] = goto(fail[u], c)——沿 u 的 fail 链回退，直到某个状态有 c 转移（否则回到根）。到达的每个状态还要沿 输出链（fail 链上的终止状态）报告：这样在 she 处能顺带报出后缀 he。
下面固定模式 {he, she, hers}、文本 "ushers"。点「下一步」逐步看：先逐模式建 Trie（节点上是入边字符、终点标模式名），再 BFS 建 fail（跨分支的 非平凡 fail 边画成紫色虚线，如 she→he；指向根的默认 fail 只在字幕说明），最后文本逐字符匹配：琥珀环是当前状态，遇无转移沿 fail 跳（虚线点亮）。走到底命中三处、且重叠： she[1,3]、he[2,3]、hers[2,5]。右侧代码随每一步同步高亮。
插入模式 "he"：沿 root 摊成一条路径到状态 "he"，末状态标记为模式终点
1function ahoCorasick(patterns: string[], text: string): [number, number][] {
2 const next: Record<string, number>[] = [{}]; // 状态 0 = root
3 const out: number[][] = [[]]; const fail = [0];
4 for (let pi = 0; pi < patterns.length; pi++) { // 建 Trie：逐模式插入
5 let s = 0;
6 for (const c of patterns[pi]) {
7 if (next[s][c] === undefined) { next.push({}); out.push([]); fail.push(0); next[s][c] = next.length - 1; }
8 s = next[s][c];
9 }
10 out[s].push(pi); // 模式终点
11 }
12 const q: number[] = [];
13 for (const c in next[0]) q.push(next[0][c]); // BFS 起点：root 的孩子 fail=root
14 while (q.length) {
15 const u = q.shift()!;
16 for (const c in next[u]) { // BFS 建 fail
17 const v = next[u][c]; q.push(v);
18 let f = fail[u];
19 while (f && next[f][c] === undefined) f = fail[f]; // 沿父的 fail 找 c 转移
20 fail[v] = next[f][c] !== undefined && next[f][c] !== v ? next[f][c] : 0;
21 out[v] = out[v].concat(out[fail[v]]); // 输出链合并
22 }
23 }
24 const hits: [number, number][] = []; let s = 0;
25 for (let i = 0; i < text.length; i++) {
26 while (s && next[s][text[i]] === undefined) s = fail[s]; // 无转移沿 fail 跳
27 s = next[s][text[i]] ?? 0;
28 for (const pi of out[s]) hits.push([pi, i]); // 报告命中（含输出链重叠）
29 }
30 return hits;
31}
模式集{he, she, hers}
文本ushers
已建状态3 / 8
fail 指针 = 多模式的 π
建 Trie：所有模式塞进前缀树，共享公共前缀。
建 fail（BFS）：fail[v] = goto(fail[父], 边字符)，沿 fail 链回退。
匹配：文本指针不回退；无转移沿 fail 跳；沿输出链报告所有命中。
复杂度：O(n + m + z)（文本长 + 模式总长 + 命中数）。
把它和 KMP 对照：KMP 在一条链上用 π 跳，AC 自动机在一棵 Trie上用 fail 跳——同一个「失配就退到最长可用后缀」的思想，从单模式推广到多模式。这也是很多敏感词过滤、生物序列比对、入侵检测里多关键词扫描的底层引擎。
