自动机原理 关键点 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节点需要记录自身也是一个终结节点,最后输出,不然就会造成匹配失败。
更多推荐
AC自动机原理 关键点 fail指针
发布评论