1. 先搞懂AC自动机到底解决了什么问题如果你已经学过KMP知道它能在 O(n) 时间内从一篇文章里找出一个模式串那当你遇到“同时查找几千个敏感词、过滤几十万条日志、匹配一整本字典里的单词”这种需求时KMP就彻底不够用了——你总不能让每个模式串都对文本跑一遍KMP模式串一多复杂度直接乘上去现实场景根本吃不消。AC自动机Aho-Corasick Automaton的多模式匹配能力就是为这种场景设计的。它的核心价值一句话就能说清把全部模式串构建成一棵带失配指针的Trie树让文本流只扫一遍就能同时找出所有模式串的所有出现位置。时间复杂度是O(文本长度 模式串总长度 匹配次数)和模式串的数量基本无关这是它最恐怖的优势。我第一次真正被AC自动机震撼到是在做日志清洗的时候。几万条规则模式串往日志全文上一跑用正则逐条匹配跑了三个多小时换成AC自动机构建一次、匹配一遍十几分钟就出结果了。从那一刻起我就觉得这个算法值得彻底吃透。这篇博客不打算按教科书套路从定义开始念。从工程落地和应试实战两个角度把Trie构建、fail指针、匹配逻辑、代码实现、复杂度、常见坑一次讲透。如果你已经懂Trie和KMP的基本思想这篇文章能直接帮你把AC自动机焊死在脑子里如果这两个前置还比较模糊文中也会有补全。提示AC自动机不是“Trie KMP”这么简单的口号。它真正的难点在于fail指针的语义理解以及匹配时“顺着fail链跳转”这个动作到底在干什么。这两点搞明白了代码不过是翻译而已。2. 从Trie树到自动机核心设计思路2.1 Trie树是整个结构的地基AC自动机并不复杂它首先是一棵Trie树。Trie树大家应该都熟悉把一组字符串按字符逐层插入树中每条从根到某个标记节点的路径代表一个模式串。比如模式串集合是{she, he, hers, his, s}插入后会形成一棵公共前缀共享的树。用结构体数组竞赛和工程里最常见的做法表示节点struct Node { int child[26]; // 子节点指针用数组模拟-1表示不存在 int fail; // 失配指针这是AC自动机的灵魂 int cnt; // 标记该节点是否为一个模式串的结尾 };Trie的构建本身没什么难点逐字符插入即可。关键在于纯Trie做多模式匹配时一旦匹配失败你只能回到根节点重新开始这就是O(n*m)的根源。AC自动机要消灭的就是这种“从头再来”。2.2 fail指针到底在指向什么这是全篇最关键的概念我尽量用大白话拆开。假设你现在正在文本串上匹配已经匹配到了节点u文本的下一个字符是c。如果u有孩子节点vc那很好直接走过去匹配长度加1。但如果u没有c这个孩子怎么办朴素做法是“回退到根再试”但这样会丢失已经匹配的部分前缀信息。AC自动机的做法是跳到另一个节点继续尝试这个节点就是fail[u]。fail[u]的准确定义是从根到节点u形成的字符串的所有后缀中能找到的最长的、且是某个模式串前缀的那个后缀对应的节点。这句话有点绕举例子。假设模式串有abc和bc你正在匹配abcd已经匹配到abc这个节点字符串abc此时下一个字符是d但abc没有子节点d。这时候abc的后缀有bc和c。其中bc恰好是模式串bc的前缀也是模式串本身但先不展开所以fail[节点abc]应该指向节点bc。于是匹配流程变成在abc处失配跳到fail指向的bc节点再看bc节点有没有子节点d。如果有继续往下走如果没有再跳fail。这样就把bc这段已经匹配过的信息保留了下来不用回到根重新读一遍。理解fail的关键就一句话fail指针保存的是当前已匹配字符串的最长真后缀且这个后缀必须是某个模式串的前缀。它和KMP的next数组本质上一模一样只是KMP的next针对单个模式串AC自动机的fail面向整棵Trie树上的所有路径。2.3 为什么用BFS构建fail而不是DFS这是面试里经常被追问的细节。构建fail指针的过程必须用广度优先搜索BFS不能DFS。原因很直接fail[u]指向的节点深度必然小于u。因为一个字符串的真后缀比它本身短fail指向的节点对应的字符串一定更短因此深度更小。只有在浅层节点的fail全部计算完毕后深层节点的fail才有依据。BFS天然按层遍历先处理完所有深度为1的节点即根的直接孩子再处理深度为2的以此类推。如果你用DFS一路扎到最深某个深层节点需要依赖的浅层fail可能还没算好就会出错。具体构建时根节点的孩子节点的fail全部指向根节点。根节点本身的fail一般也设为指向自己或者用-1占位然后在查询时特判两种写法都行我习惯用指向根的方式简化逻辑。void buildFail() { queueint q; for (int i 0; i 26; i) { if (root.child[i] ! -1) { fail[root.child[i]] root; // 第一层节点的fail直接指向根 q.push(root.child[i]); } } while (!q.empty()) { int u q.front(); q.pop(); for (int c 0; c 26; c) { if (u.child[c] ! -1) { // 子节点的fail是父节点fail的对应子节点 fail[u.child[c]] u.fail.child[c]; q.push(u.child[c]); } else { // 优化把空指针直接指向fail链上最接近的可用子节点 u.child[c] u.fail.child[c]; } } } }注意代码里的这个优化当孩子节点不存在时直接把child[c]指向fail指针节点的child[c]。这个操作叫“补全空指针”或“虚拟转移”把Trie补成了一棵真正的自动机。好处是后续匹配时不用写while循环反复跳fail直接取child[c]就能一步到位。代价是改变了Trie树结构本身但在竞赛和大多数工程实现里这个优化几乎是标配因为可以避免匹配时的递归跳转大幅降低常数。如果你第一次看到这个补全操作觉得别扭我建议你分别写两种版本对比跑一下感触会更深。没有补全的版本需要在失配时不断执行“u fail[u]”直到有对应子节点或者回到根补全后的版本只需要执行“u u.child[c]”一次。两种逻辑等价但后者写起来爽、跑起来快。3. 匹配过程文本流怎么在自动机上跑3.1 单次匹配的核心逻辑自动机构建完成后匹配就变得异常简单。维护一个当前节点u初始指向根。对文本串的每个字符c执行两步第一步转移u u.child[c]。因为有补全操作这行代码已经包含了失配时的fail跳转逻辑不需要额外判断了。第二步统计从u开始顺着fail链往上走把所有经过的节点的计数都累加起来。因为这些节点代表的字符串全都是当前匹配位置的后缀而且是模式串前缀的后缀——也就是说它们都是已经完整匹配成功的模式串。第二步的“顺着fail链往上走”是AC自动机匹配中最容易漏掉的动作。我见过很多人只统计了当前节点u漏掉了所有fail祖先导致漏报。你想想文本串是hishers模式串是{she, he, hers}匹配到hers这个节点时当前节点是hers但hers的后缀s对应的模式串she并没有被统计。你根本不需要“重新匹配”一次顺着fail链走就能把she的计数也加上。这一下就把暴力匹配中需要反复回溯的工作量全消化掉了。int query(const char* text) { int u root; // root 通常为 0 int res 0; for (int i 0; text[i]; i) { int c text[i] - a; u u.child[c]; // 一步转移内部已包含fail跳转 for (int v u; v ! root; v fail[v]) { // 加上当前节点本身以及所有fail祖先的模式串计数 res cnt[v]; // 如果只统计出现次数可以顺手把cnt[v]清零避免重复统计 } } return res; }这个for循环就是常说的“顺着fail链收集答案”。你每走一步当前节点u对应的字符串是“以当前位置结尾且能匹配上的最长字符串”它的所有fail祖先对应的是“这个最长字符串的各个后缀中恰好也是模式串前缀的那些”。把它们全部加上就得到了“以当前位置结尾的所有模式串匹配”。3.2 匹配复杂度为什么是O(n)补全后的转移是O(1)的。但每次转移后都要跑一个“顺着fail链收集答案”的循环这个循环最坏情况下会不会把复杂度拖到O(n * L)L是fail链长度答案是要分情况看的。在纯计数场景下如果你统计完就清零每个节点最多被访问一次因为计数为0就可以停了或者你显式置0总复杂度就是O(n)收集循环均摊O(1)。但如果需要统计所有出现次数且不允许清零或者需要输出所有匹配位置那最坏情况下每次转移确实都要走整条fail链复杂度会退化到O(n * L)。此时你就需要一些精妙的后缀链接优化或者用fail树上的差分统计——这个进阶技巧后面单独写。理解复杂度不能只背结论要理解“为什么大部分时候每个节点只被遍历一次”。匹配时你沿着文本走每次转移都在向前推进而fail链收集是从当前节点向上深度变浅走。一个节点被收集过一次后如果计数置零下一次再路过它就不会再走了。这样就保证了整体访问次数和节点总数同阶。3.3 动态规划视角把自动机当状态机用如果说上面的匹配过程属于“基础用法”那AC自动机真正的高级用法是拿它当状态机做DP。很多字符串尤其是基因序列、协议报文相关的题目会要求“长度为N的不包含任何模式串的字符串有多少种”。这时候AC自动机的角色就变了你不拿它去匹配文本而是把它的每一个节点当成一个状态然后在上面跑动态规划。具体来说设dp[i][u]表示“已经构造了长度为i的字符串当前匹配状态停在节点u且全程没有匹配到任何模式串”的方案数。转移时枚举下一个字符c从u转移到u.child[c]。只要目标节点及其fail祖先中没有任何一个模式串结尾标记这个转移就是合法的。这个思路在字符串计数、基因序列设计、密码学安全规则校验里都是标配。我第一次用AC自动机跑DP的时候最大的感慨是这玩意儿不只是一个“查找工具”它把“所有前缀信息”压缩在了一棵状态机里简直是为字符串DP量身定做的容器。你要想把字符串类动态规划题刷明白AC自动机是绕不开的基础设施。4. 完整实现从建树到匹配的一体化代码4.1 C实现竞赛常用写法直接给一个能跑的完整实现。这个版本用的是数组模拟节点支持26个小写字母。字符集要扩大时可以把child[26]换成map或者字典树套哈希原理不变。#include bits/stdc.h using namespace std; const int MAXN 500000; // 节点总数上限按模式串总长度定 const int SIGMA 26; // 字符集大小 struct Node { int child[SIGMA]; // 子节点编号-1表示空构建时会被补全 int fail; // 失配指针 int cnt; // 模式串结尾标记这个节点上有几个模式串结束 } tr[MAXN]; int tot; // 节点总数 // 初始化 void init() { tot 0; memset(tr[0].child, -1, sizeof(tr[0].child)); tr[0].fail 0; tr[0].cnt 0; } // 插入一个模式串 void insert(const char* s) { int u 0; for (int i 0; s[i]; i) { int c s[i] - a; if (tr[u].child[c] -1) { tr[tot]; memset(tr[tot].child, -1, sizeof(tr[tot].child)); tr[tot].fail 0; tr[tot].cnt 0; tr[u].child[c] tot; } u tr[u].child[c]; } tr[u].cnt; // 出现次数加一也可以标记为1按需求定 } // 构建fail指针 void build() { queueint q; for (int c 0; c SIGMA; c) { if (tr[0].child[c] ! -1) { tr[tr[0].child[c]].fail 0; q.push(tr[0].child[c]); } else { tr[0].child[c] 0; // 根节点的空孩子也指向自己少一个特判 } } while (!q.empty()) { int u q.front(); q.pop(); for (int c 0; c SIGMA; c) { if (tr[u].child[c] ! -1) { int v tr[u].child[c]; tr[v].fail tr[tr[u].fail].child[c]; // fail 父fail的对应孩子 q.push(v); } else { tr[u].child[c] tr[tr[u].fail].child[c]; // 补全空指针 } } } } // 匹配文本串返回所有模式串出现次数之和 int query(const char* s) { int u 0; int ans 0; for (int i 0; s[i]; i) { int c s[i] - a; u tr[u].child[c]; // 一步转移 for (int v u; v ! 0; v tr[v].fail) { if (tr[v].cnt) { // 加上答案然后清零避免重复统计 ans tr[v].cnt; tr[v].cnt 0; } } } return ans; } int main() { init(); int n; scanf(%d, n); for (int i 0; i n; i) { char s[105]; scanf(%s, s); insert(s); } build(); char text[1000005]; scanf(%s, text); printf(%d\n, query(text)); return 0; }写这个代码的时候有几个细节值得强调第一根节点的空孩子也要指向自己。这样query里不需要判断“u是不是根、根有没有这个孩子”直接一步转移。这个细节省掉的分支判断在大量数据下非常可观。第二数组要初始化干净。我不止一次看到有人忘了memset新的节点结构导致转移动辄跳到负数下标崩溃。初始化一块内存比排查几个小时的内存错乱强太多了。第三答案计数和清零的逻辑要匹配你的需求。上面代码统计的是“所有模式串在文本中出现的总次数”如果一个模式串出现两次会算两次。如果你只需要判断“是否出现过”可以在插入时把结尾标记置1统计时超过0就标记命中不用累加。4.2 内存优化与字符集扩展当模式串数量巨大比如几十万个基因片段数组开法就值得斟酌了。最直接的问题如果字符集是全集ASCII256个每个节点存256个int一千万节点就是10GB内存直接爆。这时候有几种解法用mapint, int存储子节点牺牲时间换空间查询O(logSIGMA)。用有序数组加二分查找保持内存紧凑查询O(logSIGMA)。用双数组TrieDouble-Array Trie这是工业界处理超大规模词典的标配也是AC自动机工程化的主力形态后续值得单独开一篇讲。竞赛中默认26个小写字母数组写法的确够用。但你在实际工程项目里如果上来就用二维数组存英文26处理敏感词库几万个词也还撑得住如果处理的是中日韩字符或UTF-8字节流就必须针对性设计。理解字符集大小怎么影响节点结构和内存是AC自动机从“会写模板”走向“能落地”的分水岭。5. 实战案例敏感词过滤系统的落地要点5.1 需求拆解与方案选型拿实际工程最常见的场景——敏感词过滤——来完整走一遍。假设你有一个论坛用户发帖内容需要实时过滤几千个敏感词。用AC自动机的解法是启动时或敏感词库更新时把所有敏感词插入Trie构建fail。对每条用户文本执行query找出命中的敏感词。根据业务需求要么拒绝发布、要么替换成*号、要么记录日志。看起来很简单但真实工程里有几个AC自动机“纯模板”之外的问题需要处理第一敏感词库是动态的。运营可能随时加词。如果每次加词都全量重建fail几万个词重建一次很快毫秒级问题不大但如果词库百万级、重建需要数百毫秒甚至秒级就必须引入“双缓冲”——一份线上正在服务的自动机一份后台重建的备胎重建完成再原子切换。这套路在配置热更新领域很常见本质就是读写分离。第二命中之后是真的“替换”还是“标红”。如果是替换你需要把文本里所有命中的区间找出来然后合并重叠区间。这里有个坑AC自动机匹配找到的命中区间是重叠的。比如文本“hershe”模式串{he, she, hers}命中“he”位置0-1、“hers”位置0-3、“she”位置2-4。简单地把每个命中都替换掉会出现重复替换、下标错乱的问题。正确做法是先收集所有区间做一次区间合并再统一替换。5.2 一个容易踩的坑模式串之间的包含关系假设模式串是{abc, bc}文本是abc。匹配过程走到节点abc顺着fail链收集时fail[abc]指向bcbc也是一个模式串计数自然被加上。这在AC自动机的设计里是自动完成的不需要额外逻辑。但如果我没有在build里把fail链正确建好或者收集时忘了向上走就会漏掉bc。漏报的这个“bc”恰恰是包含关系的体现模式串A包含模式串BB是A的后缀。这提醒我们测试用例一定要覆盖模式串互相包含的情况很多模板背得很熟的人也会在这里翻车。5.3 工程里的性能调优实录我之前做过一个日志清洗工具规则几千条日志单条最长几万字符。AC自动机本身匹配很快但第一次上线跑完后发现性能不够理想排查后发现瓶颈不在匹配而在“每次命中都要格式化输出位置信息”。后来做的优化是构建时额外记录每个节点对应模式串的长度或编号列表命中时直接取用不用再从fail链回溯找是哪个模式串。用位图标记命中规则编号最后统一汇总避免在循环里频繁做字符串拼接。对超长文本做分块处理每块之间保留上一条fail链状态保证跨块的连续匹配准确。第一条优化在match循环里非常值钱。因为每走一步可能要统计fail链上的多个节点每次都要访问数组缓存不友好。如果提前对每个节点预处理“从它开始向上fail链上有哪些模式串结尾”并用邻接表存好匹配时直接遍历这个邻接表把内存随机访问次数降下来。说到底AC自动机算法本身的高效在工程里还要靠数据结构与缓存友好的设计才能最大化发挥。这部分经验是单纯刷题背模板永远学不到的。6. 常见问题与排查技巧实录6.1 死循环匹配指针打转症状query程序跑起来卡死或者无限循环。原因很大概率是fail链出现了环。正常情况下fail[u]的深度小于ufail链一直往浅层走最终回到根节点不可能成环。出现环的唯一可能是build时fail赋值错误比如把某个节点的fail指向了它自己或指向了后继节点。排查方法写一个小工具对每个节点打印它的fail指向关系检查是否出现“深度不减”的边。更直接的方式是在build里加入断言assert(deep[fail[u]] deep[u])。养成这个习惯能省下很多调试时间。另一个可能原因补全空指针时把某个节点的child[c]指向了自己但它的fail又指回了自己形成“自环”。在根节点做特殊处理时最容易出现这种问题。建议用较短的测试数据逐过程单步调试看状态转移是否符合预期。6.2 漏报有些模式串没被统计到症状文本里明明有敏感词结果一个都没查出来或者少查了。最常见的三个原因第一忘了顺着fail链收集答案。只统计了当前节点u的cnt没有统计u的fail祖先。这是新手最容易犯的错。第二模式串插入后结尾标记混乱。比如多次插入同一个串末尾cnt加了多次导致统计时数值不对。需要明确cnt的语义。第三构建fail时顺序错了。用DFS而非BFS导致深层节点的fail指向还没来得及构建的浅层节点。这一步的排查很简单打印中间变量即可。6.3 误报不该命中的被命中了症状文本中明明没有这个模式串结果报告命中了。大概率是字符映射出了问题。比如模式串包含大写字母而query时统一减了‘a’大小写混在一起。或者数据输入里混入了数字、符号字符集定义和实际数据不一致。另一个可能是补全空指针时“补过头”。补全逻辑如果写错比如根节点的空孩子被补到根自身匹配时任何不在模式串中的字符都会把状态保持在根上这是合理的。但如果某个非根节点的空孩子被错误补成了它自己的孩子就会出现“凭空”多出来的转移。这个例子比较极端但真有人踩过。6.4 模式串含空串或者重复串空串如果插入空字符串insert函数里根本不会进入循环u停在根节点最后给根的cnt加一。这会导致query统计时从任何节点向上走到根都会把根上的计数加进去直接污染结果。业务上一般不允许空模式串实现的防御方式是在insert入口判断if (s[0] \0) return。重复串如果同一个模式串出现多次要根据业务考虑是要累积计数还是去重标记。工程上敏感词库一般会去重竞赛题有时专门考重复串的累积语义读题时多留个心眼。6.5 内存爆炸如果模式串总长度几十万每个节点开固定26长度的int数组那内存是26 * 4字节 * 节点数。50万节点就是5200万字节52MB能扛住。但节点数到千万级就是520MB起步很多在线评测系统会直接判MLE。解决办法能用short就用short如果节点数小于65535子节点索引short足够。用map或unordered_map按需分配。用双数组Trie压缩。工程上还有一种思路模式串分片构建比如把几千个模式串分成几个自动机轮询匹配用多个小自动机换总内存。但这种方法会在文本上重复扫描要以时间为代价取舍时需要实测数据支撑。7. 我对AC自动机的使用体会写代码十年字符串相关的算法里AC自动机是我觉得“投入产出比”最高的一个。它站在Trie和KMP两个巨人的肩膀上解决的是实际需求里最频繁出现的“多模式匹配”问题而且思想极其优雅——把失配时的信息复用做到极致让文本只需要被扫描一次。如果你现在正处于“背模板但不懂原理”的阶段我的建议是不要止步于会用一定要亲手把fail链的过程画一遍最好能自己先尝试推导再对照标准实现修正。这一步走通了你对自动机、对“状态转移”的理解会有一个质的飞跃。后面再接触后缀自动机SAM、后缀数组都会顺畅很多。如果你正准备用AC自动机解决工程问题我还有几条实操经验想分享先做小规模验证再上全量数据。用几百条文本、几十个模式串验证逻辑比直接上生产环境调试要高效得多。注意文本流和匹配状态的关系。如果文本是流式的、分段的要确保跨段的匹配状态被正确保存否则边界处会漏报。典型例子上一段结尾是“abc”下一段开头是“def”模式串是“bcde”如果分段处理时不保留上一段的匹配状态就会漏掉这个跨段命中。优先把“计数清零”和“答案收集”结合起来。一次匹配后清空命中节点的cnt可以防止重复计数也能利用“cnt为0就停止向上跳”加速非命中链的遍历。根据场景选择合适的使用模式比盲目套模板有用得多。以后有时间我打算再把后缀自动机、fail树统计、双数组Trie这几个相关话题都写成连载它们和AC自动机配合起来基本能覆盖字符串处理里80%以上的实际问题。这篇就先到这里有疑问的可以在评论区留言我看到都会认真回复。
1. 先搞懂AC自动机到底解决了什么问题如果你已经学过KMP知道它能在 O(n) 时间内从一篇文章里找出一个模式串那当你遇到“同时查找几千个敏感词、过滤几十万条日志、匹配一整本字典里的单词”这种需求时KMP就彻底不够用了——你总不能让每个模式串都对文本跑一遍KMP模式串一多复杂度直接乘上去现实场景根本吃不消。AC自动机Aho-Corasick Automaton的多模式匹配能力就是为这种场景设计的。它的核心价值一句话就能说清把全部模式串构建成一棵带失配指针的Trie树让文本流只扫一遍就能同时找出所有模式串的所有出现位置。时间复杂度是O(文本长度 模式串总长度 匹配次数)和模式串的数量基本无关这是它最恐怖的优势。我第一次真正被AC自动机震撼到是在做日志清洗的时候。几万条规则模式串往日志全文上一跑用正则逐条匹配跑了三个多小时换成AC自动机构建一次、匹配一遍十几分钟就出结果了。从那一刻起我就觉得这个算法值得彻底吃透。这篇博客不打算按教科书套路从定义开始念。从工程落地和应试实战两个角度把Trie构建、fail指针、匹配逻辑、代码实现、复杂度、常见坑一次讲透。如果你已经懂Trie和KMP的基本思想这篇文章能直接帮你把AC自动机焊死在脑子里如果这两个前置还比较模糊文中也会有补全。提示AC自动机不是“Trie KMP”这么简单的口号。它真正的难点在于fail指针的语义理解以及匹配时“顺着fail链跳转”这个动作到底在干什么。这两点搞明白了代码不过是翻译而已。2. 从Trie树到自动机核心设计思路2.1 Trie树是整个结构的地基AC自动机并不复杂它首先是一棵Trie树。Trie树大家应该都熟悉把一组字符串按字符逐层插入树中每条从根到某个标记节点的路径代表一个模式串。比如模式串集合是{she, he, hers, his, s}插入后会形成一棵公共前缀共享的树。用结构体数组竞赛和工程里最常见的做法表示节点struct Node { int child[26]; // 子节点指针用数组模拟-1表示不存在 int fail; // 失配指针这是AC自动机的灵魂 int cnt; // 标记该节点是否为一个模式串的结尾 };Trie的构建本身没什么难点逐字符插入即可。关键在于纯Trie做多模式匹配时一旦匹配失败你只能回到根节点重新开始这就是O(n*m)的根源。AC自动机要消灭的就是这种“从头再来”。2.2 fail指针到底在指向什么这是全篇最关键的概念我尽量用大白话拆开。假设你现在正在文本串上匹配已经匹配到了节点u文本的下一个字符是c。如果u有孩子节点vc那很好直接走过去匹配长度加1。但如果u没有c这个孩子怎么办朴素做法是“回退到根再试”但这样会丢失已经匹配的部分前缀信息。AC自动机的做法是跳到另一个节点继续尝试这个节点就是fail[u]。fail[u]的准确定义是从根到节点u形成的字符串的所有后缀中能找到的最长的、且是某个模式串前缀的那个后缀对应的节点。这句话有点绕举例子。假设模式串有abc和bc你正在匹配abcd已经匹配到abc这个节点字符串abc此时下一个字符是d但abc没有子节点d。这时候abc的后缀有bc和c。其中bc恰好是模式串bc的前缀也是模式串本身但先不展开所以fail[节点abc]应该指向节点bc。于是匹配流程变成在abc处失配跳到fail指向的bc节点再看bc节点有没有子节点d。如果有继续往下走如果没有再跳fail。这样就把bc这段已经匹配过的信息保留了下来不用回到根重新读一遍。理解fail的关键就一句话fail指针保存的是当前已匹配字符串的最长真后缀且这个后缀必须是某个模式串的前缀。它和KMP的next数组本质上一模一样只是KMP的next针对单个模式串AC自动机的fail面向整棵Trie树上的所有路径。2.3 为什么用BFS构建fail而不是DFS这是面试里经常被追问的细节。构建fail指针的过程必须用广度优先搜索BFS不能DFS。原因很直接fail[u]指向的节点深度必然小于u。因为一个字符串的真后缀比它本身短fail指向的节点对应的字符串一定更短因此深度更小。只有在浅层节点的fail全部计算完毕后深层节点的fail才有依据。BFS天然按层遍历先处理完所有深度为1的节点即根的直接孩子再处理深度为2的以此类推。如果你用DFS一路扎到最深某个深层节点需要依赖的浅层fail可能还没算好就会出错。具体构建时根节点的孩子节点的fail全部指向根节点。根节点本身的fail一般也设为指向自己或者用-1占位然后在查询时特判两种写法都行我习惯用指向根的方式简化逻辑。void buildFail() { queueint q; for (int i 0; i 26; i) { if (root.child[i] ! -1) { fail[root.child[i]] root; // 第一层节点的fail直接指向根 q.push(root.child[i]); } } while (!q.empty()) { int u q.front(); q.pop(); for (int c 0; c 26; c) { if (u.child[c] ! -1) { // 子节点的fail是父节点fail的对应子节点 fail[u.child[c]] u.fail.child[c]; q.push(u.child[c]); } else { // 优化把空指针直接指向fail链上最接近的可用子节点 u.child[c] u.fail.child[c]; } } } }注意代码里的这个优化当孩子节点不存在时直接把child[c]指向fail指针节点的child[c]。这个操作叫“补全空指针”或“虚拟转移”把Trie补成了一棵真正的自动机。好处是后续匹配时不用写while循环反复跳fail直接取child[c]就能一步到位。代价是改变了Trie树结构本身但在竞赛和大多数工程实现里这个优化几乎是标配因为可以避免匹配时的递归跳转大幅降低常数。如果你第一次看到这个补全操作觉得别扭我建议你分别写两种版本对比跑一下感触会更深。没有补全的版本需要在失配时不断执行“u fail[u]”直到有对应子节点或者回到根补全后的版本只需要执行“u u.child[c]”一次。两种逻辑等价但后者写起来爽、跑起来快。3. 匹配过程文本流怎么在自动机上跑3.1 单次匹配的核心逻辑自动机构建完成后匹配就变得异常简单。维护一个当前节点u初始指向根。对文本串的每个字符c执行两步第一步转移u u.child[c]。因为有补全操作这行代码已经包含了失配时的fail跳转逻辑不需要额外判断了。第二步统计从u开始顺着fail链往上走把所有经过的节点的计数都累加起来。因为这些节点代表的字符串全都是当前匹配位置的后缀而且是模式串前缀的后缀——也就是说它们都是已经完整匹配成功的模式串。第二步的“顺着fail链往上走”是AC自动机匹配中最容易漏掉的动作。我见过很多人只统计了当前节点u漏掉了所有fail祖先导致漏报。你想想文本串是hishers模式串是{she, he, hers}匹配到hers这个节点时当前节点是hers但hers的后缀s对应的模式串she并没有被统计。你根本不需要“重新匹配”一次顺着fail链走就能把she的计数也加上。这一下就把暴力匹配中需要反复回溯的工作量全消化掉了。int query(const char* text) { int u root; // root 通常为 0 int res 0; for (int i 0; text[i]; i) { int c text[i] - a; u u.child[c]; // 一步转移内部已包含fail跳转 for (int v u; v ! root; v fail[v]) { // 加上当前节点本身以及所有fail祖先的模式串计数 res cnt[v]; // 如果只统计出现次数可以顺手把cnt[v]清零避免重复统计 } } return res; }这个for循环就是常说的“顺着fail链收集答案”。你每走一步当前节点u对应的字符串是“以当前位置结尾且能匹配上的最长字符串”它的所有fail祖先对应的是“这个最长字符串的各个后缀中恰好也是模式串前缀的那些”。把它们全部加上就得到了“以当前位置结尾的所有模式串匹配”。3.2 匹配复杂度为什么是O(n)补全后的转移是O(1)的。但每次转移后都要跑一个“顺着fail链收集答案”的循环这个循环最坏情况下会不会把复杂度拖到O(n * L)L是fail链长度答案是要分情况看的。在纯计数场景下如果你统计完就清零每个节点最多被访问一次因为计数为0就可以停了或者你显式置0总复杂度就是O(n)收集循环均摊O(1)。但如果需要统计所有出现次数且不允许清零或者需要输出所有匹配位置那最坏情况下每次转移确实都要走整条fail链复杂度会退化到O(n * L)。此时你就需要一些精妙的后缀链接优化或者用fail树上的差分统计——这个进阶技巧后面单独写。理解复杂度不能只背结论要理解“为什么大部分时候每个节点只被遍历一次”。匹配时你沿着文本走每次转移都在向前推进而fail链收集是从当前节点向上深度变浅走。一个节点被收集过一次后如果计数置零下一次再路过它就不会再走了。这样就保证了整体访问次数和节点总数同阶。3.3 动态规划视角把自动机当状态机用如果说上面的匹配过程属于“基础用法”那AC自动机真正的高级用法是拿它当状态机做DP。很多字符串尤其是基因序列、协议报文相关的题目会要求“长度为N的不包含任何模式串的字符串有多少种”。这时候AC自动机的角色就变了你不拿它去匹配文本而是把它的每一个节点当成一个状态然后在上面跑动态规划。具体来说设dp[i][u]表示“已经构造了长度为i的字符串当前匹配状态停在节点u且全程没有匹配到任何模式串”的方案数。转移时枚举下一个字符c从u转移到u.child[c]。只要目标节点及其fail祖先中没有任何一个模式串结尾标记这个转移就是合法的。这个思路在字符串计数、基因序列设计、密码学安全规则校验里都是标配。我第一次用AC自动机跑DP的时候最大的感慨是这玩意儿不只是一个“查找工具”它把“所有前缀信息”压缩在了一棵状态机里简直是为字符串DP量身定做的容器。你要想把字符串类动态规划题刷明白AC自动机是绕不开的基础设施。4. 完整实现从建树到匹配的一体化代码4.1 C实现竞赛常用写法直接给一个能跑的完整实现。这个版本用的是数组模拟节点支持26个小写字母。字符集要扩大时可以把child[26]换成map或者字典树套哈希原理不变。#include bits/stdc.h using namespace std; const int MAXN 500000; // 节点总数上限按模式串总长度定 const int SIGMA 26; // 字符集大小 struct Node { int child[SIGMA]; // 子节点编号-1表示空构建时会被补全 int fail; // 失配指针 int cnt; // 模式串结尾标记这个节点上有几个模式串结束 } tr[MAXN]; int tot; // 节点总数 // 初始化 void init() { tot 0; memset(tr[0].child, -1, sizeof(tr[0].child)); tr[0].fail 0; tr[0].cnt 0; } // 插入一个模式串 void insert(const char* s) { int u 0; for (int i 0; s[i]; i) { int c s[i] - a; if (tr[u].child[c] -1) { tr[tot]; memset(tr[tot].child, -1, sizeof(tr[tot].child)); tr[tot].fail 0; tr[tot].cnt 0; tr[u].child[c] tot; } u tr[u].child[c]; } tr[u].cnt; // 出现次数加一也可以标记为1按需求定 } // 构建fail指针 void build() { queueint q; for (int c 0; c SIGMA; c) { if (tr[0].child[c] ! -1) { tr[tr[0].child[c]].fail 0; q.push(tr[0].child[c]); } else { tr[0].child[c] 0; // 根节点的空孩子也指向自己少一个特判 } } while (!q.empty()) { int u q.front(); q.pop(); for (int c 0; c SIGMA; c) { if (tr[u].child[c] ! -1) { int v tr[u].child[c]; tr[v].fail tr[tr[u].fail].child[c]; // fail 父fail的对应孩子 q.push(v); } else { tr[u].child[c] tr[tr[u].fail].child[c]; // 补全空指针 } } } } // 匹配文本串返回所有模式串出现次数之和 int query(const char* s) { int u 0; int ans 0; for (int i 0; s[i]; i) { int c s[i] - a; u tr[u].child[c]; // 一步转移 for (int v u; v ! 0; v tr[v].fail) { if (tr[v].cnt) { // 加上答案然后清零避免重复统计 ans tr[v].cnt; tr[v].cnt 0; } } } return ans; } int main() { init(); int n; scanf(%d, n); for (int i 0; i n; i) { char s[105]; scanf(%s, s); insert(s); } build(); char text[1000005]; scanf(%s, text); printf(%d\n, query(text)); return 0; }写这个代码的时候有几个细节值得强调第一根节点的空孩子也要指向自己。这样query里不需要判断“u是不是根、根有没有这个孩子”直接一步转移。这个细节省掉的分支判断在大量数据下非常可观。第二数组要初始化干净。我不止一次看到有人忘了memset新的节点结构导致转移动辄跳到负数下标崩溃。初始化一块内存比排查几个小时的内存错乱强太多了。第三答案计数和清零的逻辑要匹配你的需求。上面代码统计的是“所有模式串在文本中出现的总次数”如果一个模式串出现两次会算两次。如果你只需要判断“是否出现过”可以在插入时把结尾标记置1统计时超过0就标记命中不用累加。4.2 内存优化与字符集扩展当模式串数量巨大比如几十万个基因片段数组开法就值得斟酌了。最直接的问题如果字符集是全集ASCII256个每个节点存256个int一千万节点就是10GB内存直接爆。这时候有几种解法用mapint, int存储子节点牺牲时间换空间查询O(logSIGMA)。用有序数组加二分查找保持内存紧凑查询O(logSIGMA)。用双数组TrieDouble-Array Trie这是工业界处理超大规模词典的标配也是AC自动机工程化的主力形态后续值得单独开一篇讲。竞赛中默认26个小写字母数组写法的确够用。但你在实际工程项目里如果上来就用二维数组存英文26处理敏感词库几万个词也还撑得住如果处理的是中日韩字符或UTF-8字节流就必须针对性设计。理解字符集大小怎么影响节点结构和内存是AC自动机从“会写模板”走向“能落地”的分水岭。5. 实战案例敏感词过滤系统的落地要点5.1 需求拆解与方案选型拿实际工程最常见的场景——敏感词过滤——来完整走一遍。假设你有一个论坛用户发帖内容需要实时过滤几千个敏感词。用AC自动机的解法是启动时或敏感词库更新时把所有敏感词插入Trie构建fail。对每条用户文本执行query找出命中的敏感词。根据业务需求要么拒绝发布、要么替换成*号、要么记录日志。看起来很简单但真实工程里有几个AC自动机“纯模板”之外的问题需要处理第一敏感词库是动态的。运营可能随时加词。如果每次加词都全量重建fail几万个词重建一次很快毫秒级问题不大但如果词库百万级、重建需要数百毫秒甚至秒级就必须引入“双缓冲”——一份线上正在服务的自动机一份后台重建的备胎重建完成再原子切换。这套路在配置热更新领域很常见本质就是读写分离。第二命中之后是真的“替换”还是“标红”。如果是替换你需要把文本里所有命中的区间找出来然后合并重叠区间。这里有个坑AC自动机匹配找到的命中区间是重叠的。比如文本“hershe”模式串{he, she, hers}命中“he”位置0-1、“hers”位置0-3、“she”位置2-4。简单地把每个命中都替换掉会出现重复替换、下标错乱的问题。正确做法是先收集所有区间做一次区间合并再统一替换。5.2 一个容易踩的坑模式串之间的包含关系假设模式串是{abc, bc}文本是abc。匹配过程走到节点abc顺着fail链收集时fail[abc]指向bcbc也是一个模式串计数自然被加上。这在AC自动机的设计里是自动完成的不需要额外逻辑。但如果我没有在build里把fail链正确建好或者收集时忘了向上走就会漏掉bc。漏报的这个“bc”恰恰是包含关系的体现模式串A包含模式串BB是A的后缀。这提醒我们测试用例一定要覆盖模式串互相包含的情况很多模板背得很熟的人也会在这里翻车。5.3 工程里的性能调优实录我之前做过一个日志清洗工具规则几千条日志单条最长几万字符。AC自动机本身匹配很快但第一次上线跑完后发现性能不够理想排查后发现瓶颈不在匹配而在“每次命中都要格式化输出位置信息”。后来做的优化是构建时额外记录每个节点对应模式串的长度或编号列表命中时直接取用不用再从fail链回溯找是哪个模式串。用位图标记命中规则编号最后统一汇总避免在循环里频繁做字符串拼接。对超长文本做分块处理每块之间保留上一条fail链状态保证跨块的连续匹配准确。第一条优化在match循环里非常值钱。因为每走一步可能要统计fail链上的多个节点每次都要访问数组缓存不友好。如果提前对每个节点预处理“从它开始向上fail链上有哪些模式串结尾”并用邻接表存好匹配时直接遍历这个邻接表把内存随机访问次数降下来。说到底AC自动机算法本身的高效在工程里还要靠数据结构与缓存友好的设计才能最大化发挥。这部分经验是单纯刷题背模板永远学不到的。6. 常见问题与排查技巧实录6.1 死循环匹配指针打转症状query程序跑起来卡死或者无限循环。原因很大概率是fail链出现了环。正常情况下fail[u]的深度小于ufail链一直往浅层走最终回到根节点不可能成环。出现环的唯一可能是build时fail赋值错误比如把某个节点的fail指向了它自己或指向了后继节点。排查方法写一个小工具对每个节点打印它的fail指向关系检查是否出现“深度不减”的边。更直接的方式是在build里加入断言assert(deep[fail[u]] deep[u])。养成这个习惯能省下很多调试时间。另一个可能原因补全空指针时把某个节点的child[c]指向了自己但它的fail又指回了自己形成“自环”。在根节点做特殊处理时最容易出现这种问题。建议用较短的测试数据逐过程单步调试看状态转移是否符合预期。6.2 漏报有些模式串没被统计到症状文本里明明有敏感词结果一个都没查出来或者少查了。最常见的三个原因第一忘了顺着fail链收集答案。只统计了当前节点u的cnt没有统计u的fail祖先。这是新手最容易犯的错。第二模式串插入后结尾标记混乱。比如多次插入同一个串末尾cnt加了多次导致统计时数值不对。需要明确cnt的语义。第三构建fail时顺序错了。用DFS而非BFS导致深层节点的fail指向还没来得及构建的浅层节点。这一步的排查很简单打印中间变量即可。6.3 误报不该命中的被命中了症状文本中明明没有这个模式串结果报告命中了。大概率是字符映射出了问题。比如模式串包含大写字母而query时统一减了‘a’大小写混在一起。或者数据输入里混入了数字、符号字符集定义和实际数据不一致。另一个可能是补全空指针时“补过头”。补全逻辑如果写错比如根节点的空孩子被补到根自身匹配时任何不在模式串中的字符都会把状态保持在根上这是合理的。但如果某个非根节点的空孩子被错误补成了它自己的孩子就会出现“凭空”多出来的转移。这个例子比较极端但真有人踩过。6.4 模式串含空串或者重复串空串如果插入空字符串insert函数里根本不会进入循环u停在根节点最后给根的cnt加一。这会导致query统计时从任何节点向上走到根都会把根上的计数加进去直接污染结果。业务上一般不允许空模式串实现的防御方式是在insert入口判断if (s[0] \0) return。重复串如果同一个模式串出现多次要根据业务考虑是要累积计数还是去重标记。工程上敏感词库一般会去重竞赛题有时专门考重复串的累积语义读题时多留个心眼。6.5 内存爆炸如果模式串总长度几十万每个节点开固定26长度的int数组那内存是26 * 4字节 * 节点数。50万节点就是5200万字节52MB能扛住。但节点数到千万级就是520MB起步很多在线评测系统会直接判MLE。解决办法能用short就用short如果节点数小于65535子节点索引short足够。用map或unordered_map按需分配。用双数组Trie压缩。工程上还有一种思路模式串分片构建比如把几千个模式串分成几个自动机轮询匹配用多个小自动机换总内存。但这种方法会在文本上重复扫描要以时间为代价取舍时需要实测数据支撑。7. 我对AC自动机的使用体会写代码十年字符串相关的算法里AC自动机是我觉得“投入产出比”最高的一个。它站在Trie和KMP两个巨人的肩膀上解决的是实际需求里最频繁出现的“多模式匹配”问题而且思想极其优雅——把失配时的信息复用做到极致让文本只需要被扫描一次。如果你现在正处于“背模板但不懂原理”的阶段我的建议是不要止步于会用一定要亲手把fail链的过程画一遍最好能自己先尝试推导再对照标准实现修正。这一步走通了你对自动机、对“状态转移”的理解会有一个质的飞跃。后面再接触后缀自动机SAM、后缀数组都会顺畅很多。如果你正准备用AC自动机解决工程问题我还有几条实操经验想分享先做小规模验证再上全量数据。用几百条文本、几十个模式串验证逻辑比直接上生产环境调试要高效得多。注意文本流和匹配状态的关系。如果文本是流式的、分段的要确保跨段的匹配状态被正确保存否则边界处会漏报。典型例子上一段结尾是“abc”下一段开头是“def”模式串是“bcde”如果分段处理时不保留上一段的匹配状态就会漏掉这个跨段命中。优先把“计数清零”和“答案收集”结合起来。一次匹配后清空命中节点的cnt可以防止重复计数也能利用“cnt为0就停止向上跳”加速非命中链的遍历。根据场景选择合适的使用模式比盲目套模板有用得多。以后有时间我打算再把后缀自动机、fail树统计、双数组Trie这几个相关话题都写成连载它们和AC自动机配合起来基本能覆盖字符串处理里80%以上的实际问题。这篇就先到这里有疑问的可以在评论区留言我看到都会认真回复。
