1. 先说清楚AC自动机到底解决什么问题如果你写过字符串匹配一定用过或者听说过KMP算法。KMP解决了“一个模式串在一个长文本里出现多少次”的问题效率是O(nm)已经非常漂亮。但现实世界更残酷的场景往往是给你一堆敏感词、一批病毒特征码、一整套词典让你在一篇文章里同时找出所有命中的词。这时候你如果用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中另一个节点vv的路径字符串是S的最长且真实存在的后缀。换句话说从u出发失配后带着当前已经匹配上的部分跳到还能匹配得上的最长后缀节点。这里我要强调“真实存在”四个字——并不是所有后缀都能对应一个节点只有存在于字典中的前缀才能被跳转。如果某个后缀在Trie里没有那这个后缀就不可能是任何模式串的前缀跳过去毫无意义。构建采用BFS。根的所有子节点它们的fail一律指向根毕竟单字符最长真实后缀只能是空串。之后每弹出一个节点u就处理它的所有子节点trie[u][i]设为v先看fail[u]有没有同样字符i的子节点有就直接把v.fail指向它没有就沿着u的fail链继续往上找一直找不到最终会指向根节点0。很多人第一次写这里时会写成一个while循环往上跳fail。经典写法长这样void build() { queueint 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() { queueint 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() { queueint 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() { vectorstring 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。这是它最大的空间成本一旦模式串数量到百万级内存会涨得很快所以巨头级词库会用双数组TrieDouble-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_mapint, vectorpairint,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自动机就成功了一半。