AC自动机
定义
定义 trie 树上的节点代表其形成的前缀
令 fail 树为 trie 树上的节点向被 fail 指针指向当前节点的点连边，形成的以 trie 树的根为根的树
\(son[\,i\,][\,now\,]\) 为 \(now\) 节点后加入字符 \(i\) 的转移节点
默认字符集为 \(O(1)\)
ACAM
解决多模式串的匹配问题
回想 kmp 的过程，最好的方法是找到一个 "border"，但是这里的 border 的定义是定义在多个模式串上的，代表已经出现过的前缀中可以与当前后缀匹配的最长的前缀的节点
好吧，确实有些繁琐，如果还有不明白的，可以去这篇日报看看
好了，借助 acam，现在我们可以做到多模式串的匹配了
能不能再给力一点啊
不难看出，实际上，连完 fail 指针的 trie 树已经具备了描述当前后缀与模式串的前缀的匹配情况的能力了
举个例子，对于主串串的一个后缀而言，如果我们能够在模式串中找到一个前缀，使两者相等，那这个后缀就是对于匹配而言，就是有意义的，反之，无论这个后缀怎么扩展，都因为找不到与其相匹配的前缀而失配，所以我们可以直接抛弃这个后缀
上面的话实际上就是在描述主串在 trie 树上游走的过程，抛弃后缀实际上就是跳回根节点，而所有的匹配都可以通过跳 fail 来查到
所以acam的节点实际上描述了一类串的匹配情况，我们可以借助这一点，而解决一类与匹配有关的问题
P4052 文本生成器
正难则反，我们选择描述不与任何串匹配的状态，这样简单了不少
一个节点涵盖了一种状态，所以可以以 acam 的节点为主状态，进行 DP
定义 \(f_{i,j}\) 跳到 acam 节点 \(i\) 上，串长度为 \(j\) 的方案数，则有方程：
同时，可以根据 fail 来判出这个节点是否有成功的匹配，如果有，就可以跳过了
P2322 最短母串问题
不推荐上 LOJ 交这题，数据水的和那啥似的…
这题就如出一辙了，状压一下，然后就可以跳fail找到匹配的串究竟是哪一个，就可以了
但这题卡空间，请注意空间常数
总结一下，acam 上 DP 是一类比较套路的题型，我们可以通过 acam 刻画出当前节点的匹配情况，然后进行 DP 就可以了
能不能再给力一点啊
众所周知，kmp 有一个叫失配树的东西，可以用来刻画两个前缀的最长公共 border
考虑将这个东西放到 acam 上，这就构成了 fail 树
fail 树有下列几个性质：
fail树上的节点都是在trie树上对应的前缀fail树上一个前缀的祖先是在其他的模式串中出现过的后缀
然后就是一句看似像废话，但是实际上概括了 fail 树性质的话：子串一定是前缀的后缀
不懂的话，就先看题吧
P3796 AC自动机(加强版)
这里采用一个思想，主串实际上就是 fail 树上的若干节点
那这题就简单了，建出 fail 树对于，将主串拆分为若干节点并在节点上加一，对于每一个节点，统计其子树内的和就可以了
为什么呢，因为子串一定是前缀的后缀，对于这个前缀，他的子树内的节点一定是以自己为后缀的，所以自己一定出现在这个串内
P5357 AC自动机(二次加强版)
这题不用什么拓扑建图，直接拍上去一个fail树，你就会惊喜地发现过了
P2414 阿狸的打字机
简化一下题意，给你多个字符串，询问第 \(i\) 个字符串在第 \(j\) 个字符串中出现的次数
这题也比较板子，可以在 trie 树上 dfs ，然后在 fail 树上加一，再处理询问就可以了
P5840 Divljak
题意：动态加入主串，求模式串中有多少个串可以与主串集合匹配
建出 fail 树，将主串分成节点，在节点上加一，在节点的祖先上统计子树和就可以了
但是这样有个麻烦，就是一个串可能被统计多次，所以要借助一下树论，将拆出来的节点按照 dfs 序排序，然后再在 lca 处减一就可以了