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"，末状态标记为模式终点
fail 指针 = 多模式的 π
建 Trie：所有模式塞进前缀树，共享公共前缀。
建 fail（BFS）：fail[v] = goto(fail[父], 边字符)，沿 fail 链回退。
匹配：文本指针不回退；无转移沿 fail 跳；沿输出链报告所有命中。
复杂度：O(n + m + z)（文本长 + 模式总长 + 命中数）。
把它和 KMP 对照：KMP 在一条链上用 π 跳，AC 自动机在一棵 Trie上用 fail 跳——同一个「失配就退到最长可用后缀」的思想，从单模式推广到多模式。这也是很多敏感词过滤、生物序列比对、入侵检测里多关键词扫描的底层引擎。
