AC 自动机

『我从来没有会过任何串串科技。』
AC 自动机

相当于多个 KMP。也就是多个模板字符串上搞某种匹配问题。
建 AC 自动机

假设我有 \(n\) 个字符串为 \(abc,bcd,bd,c\)（\(n=4\)）。
首先我们对 \(n\) 个字符串建立 Trie 树。长这样：【图】。
如果我们有个匹配串为 \(abcdbc\)，那么在这棵 Trie 树上暴力匹配会似。但是当我们匹配完 \(abc\) 这个串之后直接跳到 \(bcd\) 对应的 \(c\)，就可以大大节省时间复杂度。那么这里称一个节点 \(x\) 失配之后跳到的节点 \(y\) 为 \(x\) 的失配指针对应的点。在例子中 \(abc\) 的 \(c\) 对应节点的失配指针所对的节点就是 \(bcd\) 的 \(c\)。
对于失配指针，有个性质：如果 \(x\) 的失配指针指向 \(y\)，那么 \(root \to y\) 形成的字符串应为 \(root \to x\) 形成的字符串的后缀。那么我们就可以找失配指针了，失配指针应该是在 Trie 上 \(root \to y\) 为 \(root \to x\) 后缀的 \(y\) 中，最大的 \(dep_y\) 对应的点。
现在我们来求失配指针。首先，第一层的点的失配指针为 \(root\)，第 \(i\) 层的失配指针的 \(dep\) 一定小于 \(i\)。那么求 \(x\) 的失配指针的时候只需要看 \(x\) 的父亲的失配指针对应的点 \(y\) 的那个和 \(x\) 相同值的点了（1）。如果不存在相同值的点，那就不存在了，因为如果存在，那么它的父亲一定会有这个出边，又因为 Trie 上不存在两个不同节点 \(root\) 到它形成的字符串相同，所以不可能。如果节点 \(x\) 没有值为 \(y\) 的儿子，那么就让它的儿子变成 \(x\) 的失配指针的那个儿子（2）。
哦，我是不是说错了。我们的（1）是没有正确性的，但是如果我们加上（2）之后就有了，那个证明是唐的，删了。自行理解。
建 AC 自动机的时候可以按照深度 BFS，这样对于每个 \(x\)，我们都一定知道它父亲的失配指针了。为了方便，我们建一个虚点 \(0\)，让 \(0\) 的所有出边指向 \(root\) 节点 \(1\)，然后 \(1\) 的失配指针指向虚点。
[code]il void build(){//建 AC 自动机        queue qu;qu.push(1),tr[1].fail=0;        for(re int i=0;ians) ans^=d;            return ans;        }    };        mt19937 rnd(time(0));}using namespace yzqwq;const int N=2e5+10;struct Trie{        int ch[26],fail;}tr[N];int idx=1,id[N];int siz[N];vector e[N];il void insert(string s,int k){        int u=1;        for(re int i=0;i