【别背公式了，用桌游玩懂 AC 自动机】

别背公式了用桌游玩懂 AC 自动机作者说这不是一篇搬运文也不是翻译文。这是一个真实的、从完全看不懂到灵光乍现设计桌游的完整心路历程。如果你也被老师给的 AC 自动机代码折磨过这篇文章就是为你写的。前言那个让我崩溃的晚上老师扔给我一段 Java 代码说“这是 AC 自动机你学一下。”我打开一看只有两个类TrieNode和Trie。里面有个build()方法用 BFS 搞什么fail指针。我盯着屏幕看了半小时满脑子都是computeIfAbsent是什么黑魔法fail指针到底指向谁为什么匹配失败不回到起点网上的教程千篇一律上来就甩公式fail[child] next[fail[parent]][c]。我看得懂每一个字但合起来就是天书。于是我决定不看了自己从零推导。两天后我不仅搞懂了还设计了一套桌游来理解它。是的桌游。第一章先搞懂 Trie 树——地基不牢地动山摇1.1 递归结构Map 套节点老师的TrieNode长这样classTrieNode{MapCharacter,TrieNodechildren;// 子节点booleanisEnd;// 是否是单词结尾Stringkeyword;// 关键词原文Objectpayload;// 业务数据}关键洞察children的 value 又是TrieNode而TrieNode里又有children……这就是递归/嵌套结构。每个节点都是同一类型的对象通过引用连接起来形成一棵树。1.2 插入逻辑没有路就造路publicvoidinsert(Stringword){TrieNodenoderoot;for(charc:word.toCharArray()){nodenode.children.computeIfAbsent(c,k-newTrieNode());}node.isEndtrue;}computeIfAbsent的精髓不管有没有执行完后node一定指向字符c对应的那个节点。以apple为例最终形成的结构是root └── a └── p └── p ← 注意两个 p 不能合并 └── l └── e (*)为什么不能合并连续字符如果把两个p合并成一个那app和ap就分不清了。Trie 是无损存储每个字符必须有独立节点。1.3 前缀共享分叉才新建插入app和appleroot └── a └── p └── p (*) ← app 在这里结束 └── l └── e (*) ← apple 在这里结束app和apple共享了app这一段路径。这就是 Trie 省空间的秘密。第二章AC 自动机的顿悟——从警犬到星际指挥官2.1 暴力匹配的致命伤假设我们要在文本ushers中查找关键词he、she、hers。普通做法是双层循环外层i控制起始位置内层j往后匹配。时间复杂度O(n²)。问题在哪每次匹配失败都要回到起点重新开始。文本有 100 万字关键词有 10 万个这要嗅到什么时候2.2 核心思想走不通不回头换地图AC 自动机的灵魂就一句话当当前字符走不通时不要回到起点而是瞬移到另一个节点——这个节点代表的字符串恰好是你已经走过的路的后缀。我给它起了个名字星际传送门fail 指针。2.3 为什么需要检查 fail 链假设你存了he和sheroot ├── h → e (*) ← he └── s → h → e (*) ← she当你匹配she走到e时不仅匹配到了she同时she的后缀he也匹配到了所以走到一个节点后不仅检查它自己还要沿着 fail 链检查所有后缀节点。2.4 后缀匹配的直觉build()方法的本质是不断缩短后缀去找有没有哪条路的前缀刚好对得上。比如处理appl的l先问appl的后缀ppl有没有匹配没有。再问appl的后缀pl有没有匹配没有。再问appl的后缀l有没有匹配没有。无奈l的 fail 指向 root。这就是从长到短逐级降级的过程。第三章我的两个创新理解方法3.1 方法一大小写双树可视化build()实际上可以构建成一个新的树大写字母表示 Trie 的真实路径小写字母表示 fail 指针的虚拟路径比如S → H → E是实路而s → h → e是 fail 链上的虚路。这样两条路径的层级关系一目了然。3.2 方法二桌游化重头戏我把 AC 自动机设计成了一套回合制桌游以下是完整规则书第四章《AC 古堡探险》桌游规则书4.1 游戏配件地图Trie fail 指针ROOT ├── S │ ├── root ← S 的 fail 指向 ROOT │ └── H │ ├── root.h ← H 的 fail 指向 ROOT.H │ └── E* ← she 宝藏点 │ └── root.h.e ← E 的 fail 指向 ROOT.H.E └── H ├── root ← H 的 fail 指向 ROOT ├── E* ← he 宝藏点 │ ├── root ← E 的 fail 指向 ROOT │ └── R │ ├── root ← R 的 fail 指向 ROOT │ └── S* ← hers 宝藏点 │ └── root.s ← S 的 fail 指向 ROOT.S └── I ├── root ← I 的 fail 指向 ROOT └── S └── root.s ← S 的 fail 指向 ROOTToken棋子猎人米宝沿 Trie 实路移动AC 猎犬米宝沿 fail 虚路移动藏宝图ushers宝物清单she、he、hers4.2 游戏流程每一轮包含若干回合依次执行藏宝图指针移动阶段将指针向右移动一格探路阶段猎人行动猎人沿实路前进若无路可走则触发秘境穿越采集点判断若当前节点有*拿取宝藏卡片fail 阶段猎犬行动猎犬沿 fail 路标瞬移fail 采集点判断检查猎犬所在节点是否有*结算阶段统计本轮采集到的宝藏数确认阶段记录双方位置4.3 实战推演藏宝图ushers第一轮字符uushers ↑探路ROOT 下没有u猎人无法移动采集0failROOT 没有 fail结算0 个宝藏位置猎人 ROOT猎犬 ROOT第二轮字符sushers ↑探路ROOT 有S猎人和猎犬都移动到S采集0failS的 fail 指向 ROOT猎犬移动到 ROOT结算0 个宝藏位置猎人 ROOT.S猎犬 ROOT第三轮字符hushers ↑探路S下有H双方都移动到S.H采集0failH的 fail 指向ROOT.H猎犬移动到ROOT.HROOT.H不是 ROOT继续沿 fail 前进到 ROOT结束结算0 个宝藏位置猎人 ROOT.S.H猎犬 ROOT第四轮字符e⭐️ushers ↑探路S.H下有E双方都移动到S.H.E采集有*拿取she宝藏卡片failE的 fail 指向ROOT.H.E猎犬瞬移到ROOT.H.E有*拿取he宝藏卡片ROOT.H.E不是 ROOT继续沿 fail 到 ROOT结束结算2 个宝藏she和he一站双杀位置猎人 ROOT.S.H.E猎犬 ROOT这就是 AC 自动机的精髓走到一个节点通过 fail 链自动收集所有后缀匹配。第五轮字符r秘境穿越ushers ↑探路S.H.E没有R路大路已尽秘境穿越猎人跟随猎犬沿 fail 小路前进S.H.E的 fail 指向ROOT.H.E前进一格还剩一格检查ROOT.H.E的实路有R继续前进到ROOT.H.E.R采集0failR的 fail 指向 ROOT猎犬回 ROOT结算0 个宝藏位置猎人 ROOT.H.E.R猎犬 ROOT秘境穿越就是代码里的while (node ! root !children.has(c)) { node node.fail; }第六轮字符s⭐️ushers ↑探路H.E.R下有S双方都移动到H.E.R.S采集有*拿取hers宝藏卡片failS的 fail 指向ROOT.S猎犬瞬移到ROOT.S不是 ROOT继续沿 fail 到 ROOT结束结算1 个宝藏位置猎人 ROOT.H.E.R.S猎犬 ROOT游戏结束所有宝藏she、he、hers全部找到第五章完整代码实现importjava.util.*;/** * Aho-Corasick 自动机完整实现 * 时间复杂度O(文本长度 匹配次数) */publicclassAhoCorasickAutomaton{privatestaticclassTrieNode{MapCharacter,TrieNodechildrennewHashMap();booleanisEnd;Stringkeyword;Objectpayload;intlength;TrieNodefail;}publicstaticclassMatchResult{publicfinalintstart,end;publicfinalStringkeyword;publicfinalObjectpayload;publicMatchResult(intstart,intend,Stringkeyword,Objectpayload){this.startstart;this.endend;this.keywordkeyword;this.payloadpayload;}OverridepublicStringtoString(){returnString.format(MatchResult{start%d, end%d, keyword%s, payload%s},start,end,keyword,payload);}}privatefinalTrieNoderoot;privatebooleanbuilt;publicAhoCorasickAutomaton(){this.rootnewTrieNode();this.builtfalse;}/** 添加关键词 */publicvoidaddKeyword(Stringkeyword,Objectpayload){if(keywordnull||keyword.isEmpty())return;TrieNodenoderoot;for(charc:keyword.toCharArray()){nodenode.children.computeIfAbsent(c,k-newTrieNode());}node.isEndtrue;node.keywordkeyword;node.payloadpayload;node.lengthkeyword.length();builtfalse;}/** 构建失败指针BFS */publicvoidbuild(){QueueTrieNodequeuenewLinkedList();for(TrieNodechild:root.children.values()){child.failroot;queue.offer(child);}while(!queue.isEmpty()){TrieNodecurrentqueue.poll();for(Map.EntryCharacter,TrieNodeentry:current.children.entrySet()){charcentry.getKey();TrieNodechildentry.getValue();TrieNodefailNodecurrent.fail;while(failNode!null!failNode.children.containsKey(c)){failNodefailNode.fail;}child.fail(failNodenull)?root:failNode.children.get(c);if(child.failnull)child.failroot;queue.offer(child);}}builttrue;}/** 扫描文本找出所有匹配 */publicListMatchResultmatch(Stringtext){if(!built)thrownewIllegalStateException(请先调用 build());ListMatchResultresultsnewArrayList();TrieNodenoderoot;for(inti0;itext.length();i){charctext.charAt(i);// 走不通看星门瞬移while(node!root!node.children.containsKey(c)){nodenode.fail;}if(node.children.containsKey(c)){nodenode.children.get(c);}else{continue;}// 检查 fail 链后缀匹配TrieNodetempnode;while(temp!root){if(temp.isEnd){intstarti-temp.length1;results.add(newMatchResult(start,i,temp.keyword,temp.payload));}temptemp.fail;}}returnresults;}publicstaticvoidmain(String[]args){AhoCorasickAutomatonacnewAhoCorasickAutomaton();ac.addKeyword(he,代词);ac.addKeyword(she,代词);ac.addKeyword(hers,代词);ac.build();Stringtextushers;ListMatchResultresultsac.match(text);for(MatchResultr:results){System.out.println(r);}// 输出// MatchResult{start1, end3, keywordshe, payload代词}// MatchResult{start2, end3, keywordhe, payload代词}// MatchResult{start2, end5, keywordhers, payload代词}}}结语人类的智慧网上流传的那套 AC 自动机教程上来就甩公式、画虚线、讲 BFS。我花了两天时间从最基础的 Trie 树开始一步步推导最后灵光乍现——原来build()就是在给每个节点贴星际传送门的坐标。原来match()就是猎人走实路猎犬走虚路遇到死路就秘境穿越。原来最复杂的算法也可以变成一套能摆在桌上玩的桌游。不怕笨坚持就行。但更重要的是——不要死记硬背要创造属于自己的理解模型。那个凌晨我在回家路上看到密不透风的云层里刚好留出一小片圆形缺口月亮就在那里。我盯着它看了好久。就像那些代码、星门、fail 指针还有这一片云和月亮——都是在混沌里突然透出来的一点光。如果这篇文章对你有帮助欢迎点赞收藏有问题评论区见我不一定比你懂但我一定比你更会问问题。