周报 [200426] 周报 – AC自动机 2020年4月26日 Ahocorasick下载 # AC自动机就是在树上KMP## fail节点假设已经会了kmp的核心思想,那么fail节点就是求从根节点到当前节点的这一字符串中的最长后缀是多少。然后fail节点指向这个最长后缀的末尾。<br>比如是abcde,de那么这棵树就是 !(C:/Users/19606/Pictures/C2019y4/2.jpg)## 优化利用next数组将trie树写为trie图,树中某节点没有下一个字母,直接将此字母的next设为fail[u].next。这样就可以不停向下寻找了。此外,可以将fail[u]的cnt附加到u上,这样不用写get函数,在每遍历一个字母的时候都递归一次了。 Views: 233 上一篇 简单的图着色问题 下一篇 竞赛喜报|我校ACM集训队在第六届中国大学生程序设计竞赛中取得优异成绩 发表评论 取消回复要发表评论,您必须先登录。