AC自动机原理 关键点 fail指针

自动机原理 关键点 fail指针"/>

AC自动机原理 关键点 fail指针

前提

已经了解基础的Trie树，进一步看下AC自动机比Trie树牛皮在哪里，其实就是牛皮在fail指针可以减少匹配次数

参考

b站大法好
code
极客时间
github code

例子

好的例子是成功的一半

这个图很好地说明了fail指针的原理，还是看视频理解的好

几个关键点：

构建fail指针的时候

层次遍历构建fail指针

根节点，以及根节点的儿子，没有所谓最长后缀，fail节点都指向root

遍历到某个节点，就看父节点的fail指针fafail，如到4号的时候，看父节点2号的fail指针root的孩子，发现没有e，4号的fail也指向root；到6号的嘶吼，发现父节点3的fail指针是root，root有子节点h是2，所以6.fail=2；到9号，发现父节点6的子节点有e(4)，所以9.fail=4

查找代码怎么写

可以看到都是一个套路

0.for循环遍历输入
1、一个while循环，沿着fail指针找
2、退出while循环的时候，要么是沿着fail节点找到了下一个字符（那就移动到树的子节点），要么就是直接回到root(这样就在root打转检查输入的下一个字符)
3、然后就检查一下是不是结束的节点就好了，是的话输出。

细节

这里有个关键细节，b站的实现中，每个节点要记录多个单词的匹配。如下面的6号节点，既是she的结尾，也是he的结尾，记录的长度信息[3,2]（需要跟fail节点3号的[2]关联上）。如果没有这个信息会造成奇怪的bug，我们还真遇到过了，
如词表=[ycwc,cw]，q=ycw，ycwc的w节点需要记录自身也是一个终结节点，最后输出，不然就会造成匹配失败。