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\) 的失配指针指向虚点。
il void build(){//建 AC 自动机 queue qu;qu.push(1),tr.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,fail;}tr;int idx=1,id;int siz;vector e;il void insert(string s,int k){ int u=1; for(re int i=0;i 谢谢分享，试用一下 这个好，看起来很实用 感谢，下载保存了 谢谢分享，辛苦了 东西不错很实用谢谢分享 感谢分享 感谢分享 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 东西不错很实用谢谢分享 很好很强大我过来先占个楼 待编辑 感谢发布原创作品，程序园因你更精彩 感谢分享，下载保存了，貌似很强大 感谢分享，下载保存了，貌似很强大 用心讨论，共获提升！ 分享、互助 让互联网精神温暖你我 感谢发布原创作品，程序园因你更精彩 感谢分享，下载保存了，貌似很强大 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 前排留名，哈哈哈
页:
[1]
2