Trie图（AC自动机）总结

AC自动机构建完成后&＃xff0c;某个节点沿着Fail链向上能从长到短走到自己的所有后缀。一般的&＃xff0c;遍历主串进行匹配&＃xff0c;就是在Trie图上定向移动的过程。

构造&＃xff08;一遍 BFS&＃xff09;

1、模式匹配

主串从左到右&＃xff0c;就顺着每一个字符向下跳&＃xff0c;每一次沿着Fail链向上。这样会可重而不漏的得到模式串中的所有子串&＃xff0c;视题目要求进行操作即可。

&＃xff08;1&＃xff09;TJOI2013 单词&＃xff1a;本人的LJ做法&＃xff0c;把所有串建Trie图&＃xff0c;再把所有串拿 # 接起来&＃xff0c;然后暴力匹配。

2、利用Fail链进行预处理

&＃xff08;1&＃xff09;不可到达&＃xff08;危险&＃xff09;节点标记&＃xff1a;一个串的后缀是危险的&＃xff0c;它即是危险的

&＃xff08;2&＃xff09;某些统计&＃xff1a;到达某个串结尾处相当于匹配了它和它的所有后缀&＃xff0c;可以进行一些sigma之类的操作

3、与Trie图性质相关

&＃xff08;SDOI2005 病毒&＃xff09;模拟一个字符串在Trie图上匹配的过程&＃xff0c;危险节点不可走。在此基础上找环。

4、AC自动机相关某些题目

&＃xff08;1&＃xff09;HNOI2004 L语言 &＃xff1a;在模式串结尾记LEN&＃xff0c;一边模式匹配一边 DP&＃xff0c;

&＃xff08;2&＃xff09;USACO2015 删减&＃xff1a;在模式串结尾记LEN&＃xff0c;维护一个栈&＃xff0c;匹配成功时把栈顶上LEN个元素拿走

&＃xff08;3&＃xff09;JSOI2009&＃xff1a;密码&＃xff1a;在Trie图上进行记忆化搜索&＃xff08;记录所有串的选取状态&＃xff09;输出方案好恶心的

5、Trie图上的DP

一般的&＃xff0c;设出如下状态&＃xff1a;

&＃xff1a;做到主串第 i 个位置&＃xff0c;在Trie图上的 j 点&＃xff0c;……。

转移&＃xff1a; 使用刷表法DP&＃xff0c;必要时上矩阵进行优化。

初始状态是 。

&＃xff08;1&＃xff09;Fzoj DNA修复&＃xff1a;不能往危险节点跑&＃xff0c;然后直接。

&＃xff08;2&＃xff09;Fzoj 匹配&＃xff1a;状压&＃xff0c;&＃xff0c;Flag事先预处理。

&＃xff08;3&＃xff09;Fzoj 中等的字符串&＃xff1a;&＃xff0c; 构造矩阵转移&＃xff0c;类似求 N 条边最长路。

扔一份 暴力DP 的代码&＃xff1a;

&＃xff08;4&＃xff09;BJOI2016 打字机&＃xff1a;不可做

&＃xff08;5&＃xff09;BJOI2017 魔法咒语&＃xff1a;1-6号点暴力做&＃xff0c;7-8用转移矩阵&＃xff0c;9-10类似 Fib 那样进行转移&＃xff0c;挺毒瘤的。

6、Fail树性质&＃xff08;Fail 链自下而上的后缀关系&＃xff09;

一般用于解决与多串相关的子串计数问题。

&＃xff08;1&＃xff09;阿狸的打字机&＃xff1a;按题意模拟建 Trie 树&＃xff0c;按题意模拟在 Trie 图上跑&＃xff0c;走到&＃43;1离开-1&＃xff0c;用 BIT 维护子树和。

&＃xff08;2&＃xff09;COCI2015 Divljak&＃xff1a;先对 Alice 的串建 Trie 图&＃xff0c;由 Fail 树性质原问题等价于解决“树链求并”的计数问题&＃xff0c;解决方法我是抄题解的&＃xff1a;对链的各个底端端点按 dfs 序排序&＃xff0c;在各个点处 &＃43;1&＃xff0c;在相邻两点 LCA 处 -1&＃xff08;想一想为啥&＃xff09;。树剖求 LCA 即可。子树和仍然使用 BIT 维护。