AC 自动机: Aho-Corasick automaton, 该算法在 1975 年产生于贝尔实验室, 是著名的多模匹配算法.
今天蒟蒻林荫来复习 AC 自动机
前置芝士
KMP 算法 https://www.cnblogs.com/XLINYIN/p/11348967.html
TRIE 树 (这个不会的话出门右转幼儿园)
好吧我承认 AC 自动机要比 KMP 好理解.
如何建立一个 AC 自动机
建立一颗字典树, 其中插入操作和普通字典树的一模一样
在字典树上构造 fair 数组 (这也就是 AC 自动机与 KMP 联系起来的地方)
开始查找
如何构造一个 fair 数组?/fair 数组是个啥?
fair 数组与 KMP 中的 next 一样都是作为失配数组存在的, 而对于节点 X,fair 所存的元素是 fair[x 的父亲] 的一个与 X 相同的儿子, 如果没有 fair 指向 root.
也就是说 fair[x]= 某个与 x 节点相同的点或者 root, 并且 fair[x] 所在的链一定存在于 X 所在的这条链上, 换句话说, fair[x] 所跳转到的字符串一定是 X 所在串从 X 向前的一部分, 且一定包括 X.
至于如何求 fair, 就通过 BFS 来实现
下面来张图
红色线: root 出队, 将 h 和 s 两个点 fair 置为 root, 并将 h 和 s 入队
蓝色线: h 出队, 子节点 e 的 fair 等于自己父亲的 fair 的子节点中 e 的位置, 不存在所以为 root,e 入队, 同时 s 出队, 子节点 a 的 fair 为自己父亲的 fair 的子节点中 a 的位置不存在为 root,a 入队, 子节点 h 的 fair 为自己父亲 fair 的子节点中 h 的位置, 存在, fair[tire[now][i]]=tire[fair[now]][i];h 入队
绿色线: e 出队, 子节点 r 的 fair 等于自己父亲的 fair(root) 中子节点中 r 的位置, 不存在为 root,r 入队, a 出队, 子节点 y 的 fair 同样为 root,y 入队, h 出队, 子节点 e 的 fair 等于父亲的 fair 的子节点中 e 的位置, fair[tire[now][i]]=tire[fair[now]][i], 与左子树的 e 相连, e 入队, 子节点 r 的 fair 为 root, 入队;
这样的话 fair 数组就整理好了, 对于不存在的点, tire[now][i]=tire[fair[now]][i]. 如果这个点不存在, 那么就指向自己父亲的 fair 的对应位置. 类似于一个状态压缩, 如果当前 x 的 fair 中并没有与 x 相同的元素, 那么就前往 fair[x] 的 fair, 因为 fair[x] 代表的元素 ==x,fair[fair[x]] 代表的元素 ==fair[x] 代表的元素
- void getfail()
- {
- queue<int>q;
- for(int i=0;i<26;i++)
- {
- if(trie[0][i])
- {
- q.push(trie[0][i]);
- fail[trie[0][i]]=0;
- }
- }
- while(!q.empty())
- {
- int now=q.front();
- q.pop();
- for(int i=0;i<26;i++)
- {
- if(trie[now][i])
- {
- fail[trie[now][i]]=trie[fail[now]][i];
- q.push(trie[now][i]);
- }
- else
- {
- trie[now][i]=trie[fail[now]][i];
- }
- }
- }
- }
- FAIR
万恶的 fair 终于整理完成了
下面来说说查询
AC 自动机是用来查询原串中出现模式串次数的, 所以这里引入一个变量 tdword[x] 代表在 x 节点结尾的模式串的个数
那么查询的第一重循环一定是在 tire 上确定原串每一位的位置的, 联想到刚才 fair 的定义, 也就是说一个点如果目前与原串匹配, 那么这个点的 fair 及 fair 以上字符构成的串也一定能和原串匹配, 所以说每到达一个节点, 都要访问这个点可以通过 fair 数组所访问到的每一个点
- int query(string x)
- {
- int ans=0;
- int now=0;
- for(int i=0;i<s.size();i++)
- {
- now=trie[now][x[i]-'a'];for(int j=now;j&&tdword[j]!=-1;j=fail[j])
- {
- ans+=tdword[j];
- tdword[j]=-1;
- }
- }
- return ans;
- }
而本人的代码对应的是洛谷上 AC 自动机的模板, 该题要求统计出现模式串的种类数, 第二重循环即为根据某个点跳 fair, 如果 tdword[j]==-1 的话就代表这个点已经在之前被访问过一遍, 那么它的 fair 肯定也全部都跳完了. 所以说跳到 tdword[j]==-1 的情况就停下来.
OK, 完结撒花!
来源: http://www.bubuko.com/infodetail-3156221.html