[200426] 周报 – AC自动机

# 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