首页 > 其他 > 详细

AC自动机fail树小结

时间:2018-10-19 13:36:08      阅读:462      评论:0      收藏:0      [点我收藏+]

建议大家学过AC自动机之后再来看这篇小结

fail树就是讲fail指针看做一条边连成的树形结构

fail指针在AC自动机中的含义是指以x为结尾的后缀在其他模式串中所能匹配的最长前缀的长度

所以在模式串中一定有sq[1~fa[x]]为sk[1~x]的子串

这个性质可以解决一些问题:

单词

显然,我们在插入时在沿着tire树走时,将遍历到的所有节点的val++

最后我们的答案就是这个单词的结尾在fail树中的所有子树的val之和,因为之前的性质,

这个单词的fail树的子树节点中的所有节点,都意味着该串在其他模式串中的出现

我们并不用将fail树都建出来,然后统计

因为我们其实在求fail指针的过程中就已经有了fail树的dfs序,即每个节点入队(出队)的序列

沿着这个序列反向遍历统计一下答案就好了

未完(...)

 

AC自动机fail树小结

原文:https://www.cnblogs.com/logeadd/p/9815722.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!