AC自动机

用于解决多模式串匹配相关问题。实际上就是 KMP 在多串的扩展。

首先建出字符串的 trie 树，然后 AC 自动机只是在 trie 树上加了一些边。

只需要记住：儿子的 fail 就是 fail 的儿子，不存在的儿子直接是 fail 的儿子，然后 bfs 即可。

然后解决的问题类似于给定若干模式串，要求长度为 \(n\) 的包含模式串至少一个/不包含的字符串个数等。包含至少一个可以从所有字符串中减去不包含的即可。不包含的可以 dp 设 \(f_{i,j}\) 表示长度为 \(i\)，目前走到节点 \(j\)，没有匹配上任意一个的方案数，转移枚举下一个是什么直接走儿子即可。注意不能走到有终止节点的地方。