1. 先说清楚：AC自动机到底解决什么问题
如果你写过字符串匹配，一定用过或者听说过KMP算法。KMP解决了“一个模式串在一个长文本里出现多少次”的问题，效率是O(n+m)，已经非常漂亮。但现实世界更残酷的场景往往是：给你一堆敏感词、一批病毒特征码、一整套词典，让你在一篇文章里同时找出所有命中的词。这时候你如果用KMP一个个跑，模式串有k个，文本长度是n，最坏就是O(k*n)，词库一大就肉眼可见地卡顿。而AC自动机（Aho-Corasick Automaton）就是专门解决这个问题的——它把Trie树和KMP的失配思想揉在一起，一次扫描文本，同时匹配所有模式串，整体复杂度降到O(n + 总模式串长度)。理解它的核心，一句话：先建字典，再有指针，最后照着文本一路走。
这篇文章适合三类人：正在备战算法竞赛、笔试面试需要啃字符串算法的学生；工作中要做敏感词过滤、日志匹配、词条命中的后端工程师；以及任何对“如何高效地在文本里找词”感兴趣的读者。我会从原理讲到实现，再讲调试经验和坑，尽量用大白话把每个环节拆开，保证你看完能自己把代码写出来。
2. 思路拆解：为什么非要把Trie和KMP捆在一起
2.1 暴力匹配和三重循环的笨拙
先回顾一下朴素的多模式匹配。假设有3个模式串：he、she、his，文本是ushers。暴力做法就是枚举文本的每个起始位置，然后分别拿3个模式串去比。这个做法不仅逻辑简单，写起来也简单，可一旦词库膨胀到几千条甚至几十万条，文本一长，CPU时间的消耗就会直线上升。原因很直白：文本每个位置都要跟所有模式串重新比一轮，前面刚做过的比较结果完全没有被复用，信息被白白扔掉。
那反过来想，能不能把这些模式串先“压缩存储”，让公共前缀只存一次？能——这就是Trie树。Trie树把he、she、his这些词的公共前缀合并存储，从根节点往下走，每条路径就是一个词。
2.2 KMP的失配指针给了AC自动机灵魂
但光有Trie还不够。你在Trie里匹配时，走到某个节点发现不匹配，如果退回根节点重新开始，那所有已做过的工作还是废了。KMP算法的精髓在于：当模式串在某一位失配时，不把文本指针回退，只把模式串指针跳到下一个可能匹配的“最长公共前后缀”位置。AC自动机把这一招挪到了Trie上——在Trie的每个节点上额外维护一个fail指针（失败指针/失配指针），指向“如果当前路径匹配失败，该跳去哪个节点继续匹配”。Trie负责组织字典，fail指针负责在失配时快速转移，二者结合，文本只需要从头到尾扫描一遍，就可以收集到所有模式串的命中信息。
这也是AC自动机能保持O(n)级别的关键：文本指针永不回退，每次失配只是沿着fail链跳转，均摊下来每次跳转都是O(1)级别的代价。
2.3 整体设计：先建树，再补指针，最后匹配
整个AC自动机可以在逻辑上拆成三步：
- 把所有模式串插入Trie树，每个节点代表一个前缀；
- 对Trie树做一遍BFS（广度优先遍历），逐个节点计算fail指针；
- 用文本在带fail指针的Trie上跑匹配，采集所有命中结果。
这三个步骤对应了实现里的三个函数：insert、build、query。后面所有的代码和调试，都是围绕这三个函数展开的。先把这个三维结构记住，接下来任何一个环节都不会晕。
3. 核心细节：Trie树和fail指针到底怎么建
3.1 Trie树的节点设计
这里以C++为例。最常规的设计，每个节点包括三样东西：子节点指针（或数组）、模式串结束标记、fail指针。如果字符集是26个小写字母，可以直接用长度为26的数组；如果字符集很大，就用哈希表或者vector存边。竞赛里最常见的是数组版本：
#include <bits/stdc++.h> using namespace std; const int MAXN = 500005; // 根据模式串总量估算节点数上限 const int MAXC = 26; // 字符集大小 int trie[MAXN][MAXC]; // 子节点编号，0表示不存在 int fail[MAXN]; // fail指针 int vis[MAXN]; // 模式串结束标记，这里顺便统计词频 int tot = 0; // 当前节点总数，根节点是0 void insert(const string& s) { int cur = 0; for (char c : s) { int id = c - 'a'; if (!trie[cur][id]) trie[cur][id] = ++tot; cur = trie[cur][id]; } vis[cur]++; // 标记该节点是一个模式串的结尾 }这段代码的逻辑和标准Trie一致。注意一个细节：tot从0开始，根节点占0号，并且trie[0]这一整行全为0——这天然就成了“0表示空节点”的哨兵，将来构建fail指针时，这个约定会省掉很多边界判断。
3.2 BFS构建fail指针：核心核心再核心
fail指针的定义是：假设当前节点u的路径字符串是S，节点u的fail指向的是Trie中另一个节点v，v的路径字符串是S的最长且真实存在的后缀。换句话说，从u出发失配后，带着当前已经匹配上的部分，跳到还能匹配得上的最长后缀节点。这里我要强调“真实存在”四个字——并不是所有后缀都能对应一个节点，只有存在于字典中的前缀才能被跳转。如果某个后缀在Trie里没有，那这个后缀就不可能是任何模式串的前缀，跳过去毫无意义。
构建采用BFS。根的所有子节点，它们的fail一律指向根（毕竟单字符，最长真实后缀只能是空串）。之后每弹出一个节点u，就处理它的所有子节点trie[u][i]，设为v：
- 先看
fail[u]有没有同样字符i的子节点，有就直接把v.fail指向它； - 没有就沿着
u的fail链继续往上找； - 一直找不到，最终会指向根节点0。
很多人第一次写这里时，会写成一个while循环往上跳fail。经典写法长这样：
void build() { queue<int> q; for (int i = 0; i < MAXC; i++) { if (trie[0][i]) { fail[trie[0][i]] = 0; q.push(trie[0][i]); } } while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < MAXC; i++) { int v = trie[u][i]; if (v) { int f = fail[u]; while (f && !trie[f][i]) f = fail[f]; fail[v] = trie[f][i] ? trie[f][i] : 0; q.push(v); } } } }这个写法没有问题，逻辑也很直白。但我强烈推荐在工作项目中用下面这个优化写法，因为它利用“缺省补全”的思想，把Trie直接补成了一张完整的自动机状态转移表，后面匹配时一个while都不需要：
void build() { queue<int> q; for (int i = 0; i < MAXC; i++) { if (trie[0][i]) q.push(trie[0][i]); // 根的子节点fail本来就是0，不用显式赋值 } while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < MAXC; i++) { int v = trie[u][i]; if (v) { fail[v] = trie[fail[u]][i]; // 父节点fail的同类子节点，必已“补全” q.push(v); } else { trie[u][i] = trie[fail[u]][i]; // 自动机补全：不存在就指向fail转移后的结果 } } } }为什么第二种写法行得通？因为BFS按层推进，轮到节点u时，u的fail（深度一定小于u）已经处理完毕，trie[fail[u]][i]一定已经被填充成了一个有效值。这样每个节点缺失的边都会被填成“失配后应该跳去的位置”，整个Trie变成了一张没有死路的图。匹配时无论输入什么字符，都有确定的去处，不用再去检查“边界”，也不用回溯。
注意：这里如果用数组存子节点，
trie[u][i]本身会被覆盖改写，所以在构建结束后，你不能再拿Trie树当普通字典树去遍历，只能当作自动机来走。这一点在debug时容易把人绕晕，先有个心理预期。
3.3 丢失的匹配信息：一个经典坑
建完fail指针后还有一个很容易漏掉的操作——把每个节点的命中信息沿着fail链“合并”上去。也就是说，如果节点A的fail指向节点B，而B是某个模式串的结尾，那么匹配到A时，其实B对应的模式串也同时命中了。因为B的路径字符串是A路径字符串的后缀，前缀匹配上了，后缀自然也就匹配上了。
所以许多写法会在一开始就把这些信息累积起来：
void build() { // ... 上面的BFS ... // 在弹u的时候, 顺手做: // vis[u] += vis[fail[u]]; }这样处理之后，vis[u]就代表“当前路径上所有真实发生的模式串命中次数之和”。匹配阶段每走到一个节点，直接把该节点的vis加到答案即可，不必再跳fail链取数。这是空间换时间的常用实践，也是初学者最容易踩的坑：建完fail就去匹配，发现短模式串老是漏报，原因就在没做这个“后缀收集”。
4. 实操：匹配阶段与完整模板代码
4.1 匹配逻辑一句话：照着自动机走，走完顺手摘果实
匹配就是拿着文本字符串，从根节点出发，一个一个字符在自动机上走。每走一步，当前节点的vis如果有值，就说明有模式串命中。这里由于构建阶段已经做了后缀信息合并，所以简单累加即可：
long long query(const string& s) { long long ans = 0; int cur = 0; for (char ch : s) { int id = ch - 'a'; cur = trie[cur][id]; // 自动机已经保证了这个位置一定有合法转移 ans += vis[cur]; } return ans; }代码就这么短。你可能会惊讶，匹配居然比构建还简单——事实如此，AC自动机的复杂度全在构思和构建，匹配只是“在状态图上跑”。这也解释了为什么它很适合做成敏感词过滤的底层：构建词库一次之后，每条文本的扫描就是一趟线性的状态转移。
4.2 完整模板：从插入到匹配的C++实现
把前文所有代码拼起来，就是一份可直接运行的简洁AC自动机。这里我补一个可完整编译验证的场景：模式串["he", "she", "his", "hers"]，文本ushers。
#include <bits/stdc++.h> using namespace std; const int MAXN = 500005; const int MAXC = 26; int trie[MAXN][MAXC], fail[MAXN], vis[MAXN], tot = 0; void insert(const string& s) { int cur = 0; for (char c : s) { int id = c - 'a'; if (!trie[cur][id]) trie[cur][id] = ++tot; cur = trie[cur][id]; } vis[cur]++; } void build() { queue<int> q; for (int i = 0; i < MAXC; i++) { if (trie[0][i]) q.push(trie[0][i]); } while (!q.empty()) { int u = q.front(); q.pop(); vis[u] += vis[fail[u]]; // 后缀合并，防止漏报 for (int i = 0; i < MAXC; i++) { int v = trie[u][i]; if (v) { fail[v] = trie[fail[u]][i]; q.push(v); } else { trie[u][i] = trie[fail[u]][i]; } } } } long long query(const string& s) { long long ans = 0; int cur = 0; for (char c : s) { int id = c - 'a'; cur = trie[cur][id]; ans += vis[cur]; } return ans; } int main() { vector<string> pats = {"he", "she", "his", "hers"}; for (auto& s : pats) insert(s); build(); string text = "ushers"; cout << query(text) << '\n'; // 输出 3 return 0; }跑一遍逻辑：文本ushers中，能匹配到的模式串是she、he、hers，三处命中，输出3。你可以自己动手手工推一遍这个例子，把每个节点的fail指针画出来，走一遍ushers的状态转移，很快就能彻底理解。
4.3 Python实现：快速原型的最佳选择
如果只是做原型验证、小规模文本处理，Python版本会更友好。Python实现通常用字典存子节点，逻辑更清晰：
from collections import deque, defaultdict class AhoCorasick: def __init__(self): self.trie = [defaultdict(int)] self.fail = [0] self.output = [[]] # 每个节点挂载命中的模式串列表 def insert(self, word, idx): cur = 0 for ch in word: if ch not in self.trie[cur]: self.trie[cur][ch] = len(self.trie) self.trie.append(defaultdict(int)) self.fail.append(0) self.output.append([]) cur = self.trie[cur][ch] self.output[cur].append(idx) def build(self): q = deque() for nxt in self.trie[0].values(): q.append(nxt) while q: u = q.popleft() for ch, v in self.trie[u].items(): f = self.fail[u] while f and ch not in self.trie[f]: f = self.fail[f] self.fail[v] = self.trie[f].get(ch, 0) self.output[v] += self.output[self.fail[v]] q.append(v) def query(self, text): cur = 0 res = [] for i, ch in enumerate(text): while cur and ch not in self.trie[cur]: cur = self.fail[cur] cur = self.trie[cur].get(ch, 0) res.extend([(i + 1 - len(pats[j]), j) for j in self.output[cur]]) return res pats = ["he", "she", "his", "hers"] ac = AhoCorasick() for i, w in enumerate(pats): ac.insert(w, i) ac.build() print(ac.query("ushers"))Python版本的字典写法适合教学，但如果词库很大，性能会弱于数组版本。需要用Python做高并发敏感词过滤时，建议用array或第三方绑定的C库，别直接用纯Python扛线上流量。
4.4 复杂度分析与细节选择
构建阶段：每个模式串长度累加为L，插入是O(L)；BFS过程中每个节点、每条边只处理常数次，所以总体O(L)。匹配阶段：文本长度为n，每次转移O(1)，所以O(n)。总空间：自动机的节点数等于Trie的节点数，数组实现是节点数 * 字符集大小，26个小写字母就是节点数 * 26个int。这是它最大的空间成本，一旦模式串数量到百万级，内存会涨得很快，所以巨头级词库会用双数组Trie（Double-Array Trie）来压缩，但原理上仍然是同一套状态机思路。
顺带一提，AC自动机的时间复杂度不包含答案输出部分。如果需要把每次命中位置都精确列出来，输出本身的开销是O(命中次数)，这部分无法避免。
5. 实战案例与场景映射
5.1 敏感词过滤系统
这是AC自动机最“出圈”的应用。把敏感词库构建成自动机，然后对每条用户发言做一次线性扫描，命中就替换或拦截。相比逐词遍历，词库越大，优势越明显。大型论坛的即时过滤链路里，AC自动机几乎是标配的地基。
实际操作中，建议将词库按类别分组维护，每次更新词库时重建自动机（增量插入需要额外设计，工程上不值得，因为构建本身很快）。文本量大的话，可以把文本按行/段落分批扫描，每批次复用同一个自动机实例，避免频繁初始化。
5.2 多模式串统计与代码审计
在日志中同时统计多个错误码、在代码库中扫描多个风险函数名、在协议包里匹配多个魔数签名——凡是“一批固定特征串，去另一段长文本里找所有出现”，都是AC自动机的应用范围。你只需要把模式串换成对应的特征码，代码一行不用改。
5.3 与正则表达式的分工
很多人会问：“有正则、有grep -f，为什么还要写AC自动机？”答案在于两点：一是可控性，AC自动机的匹配逻辑完全透明，可以精确知道每个词出现的位置、次数和上下文；二是性能，正则多模式匹配底层往往也是类AC的状态机实现，但工程上你绕一层库，就多一层不可控的开销和版本差异。在核心链路上，自己实现AC自动机会更扎实。
6. 常见问题与排查技巧实录
6.1 为什么匹配结果少了/多了
“少了”最常见的原因就是前面反复强调的：构建阶段没有合并fail链上的命中信息。你走到某个节点时，它自己不是模式串结尾，但它的fail链上是一个模式串结尾，这种情况漏报率极高。多模式串里恰好有词互为后缀时（例如he和she），这个问题立刻暴露。
“多了”一般是模式串本身包含重复，或者自动机被错误构建成环。检查时拿极小数据集（两三个词、一两句话），人工把每个节点的fail画出来，跟着文本走一遍定位。不要在大数据集里肉眼debug，效率极低。
6.2 构建后Trie被改了
前面说过，优化版的构建会填充缺失的边，trie数组在构建后就不再是原来的树。如果你构建之后还想要原始Trie结构（比如要遍历所有前缀），建议在构建前深拷贝一份，或者换用不覆盖原数组的写法。这个坑，我见过不少人在调试时被绕进去，半天对不上逻辑。
6.3 内存占用过大怎么办
两个字：压缩。字符集大时，把数组转成unordered_map<int, vector<pair<int,int>>>或采用双数组Trie。但对算法竞赛或日常工具来说，数组版本仍然是首选——它快、简单、可预测。如果模式串数量超过几百万，建议提前估算节点数上限，不要依赖动态扩容。MAXN设小了会内存越界，设大了浪费。合理的做法是：节点数上限 = 所有模式串长度之和 + 1，再留10%~20%余量。
6.4 匹配时避免重复向上跳fail
在朴素写法中，如果每到一个节点都要沿fail链向上取所有匹配结果，最坏情况下每条fail链长度是模式串长度，复杂度会退化到接近O(n*L)。解法就是用空间换时间：构建阶段做信息合并，或者预处理每个节点的“命中链”，匹配阶段永远只取当前节点的聚合数据。这是AC自动机性能优化的最核心细节。
6.5 多字节字符和中文匹配的注意点
千万注意，AC自动机处理的是离散符号序列。如果直接按字节对UTF-8字符串做匹配，中文会被拆成多个字节，导致模式串错位。正确处理方式有两种：要么对文本和模式串统一按Unicode码点切分后再建自动机；要么在字节层面直接把模式串按UTF-8编码后的字节序列建Trie，匹配时同样按字节走。后者在C++里实现更直接，内存稍大，但对中英文混合文本没有两套逻辑，推荐优先尝试。
7. 我的实际体会
AC自动机是一个“原理一句话，细节一堆坑”的算法。理论上看懂了Trie+失配指针，可能20分钟就能把思路讲明白；但真正动手写出一个不出错的版本，至少要经历两三轮“构建漏合并→匹配漏报→回去补后缀信息→匹配多报→查重”的循环。我个人做这一块时最有价值的习惯是：永远准备一个极小的手推用例，每次改完代码先跑它，再上真实词库。这个习惯省下来的debug时间，远超写那几行测试代码的功夫。
另外，如果是做生产系统，不要迷信“手写AC自动机一定比库快”。C++手写版本配合数组内存池，确实可以在微秒级处理上KB文本；但Java/Python环境里，第三方库（如Java的AhoCorasick库、Python的pyahocorasick）经历过多轮优化，坑少且稳定性好。自己实现前，先评估场景——是学习巩固、竞赛算法，还是线上高并发。前者建议务必手写，后者可以先压测库再做决定。
最后再分享一个小技巧：调试fail指针时，把每一层节点的fail指向打印成一棵树，你立刻就能看出哪些节点的fail没有指向“最长后缀”。这一步做对了，AC自动机就成功了一半。
