【学习笔记】AC自动机
目录
一、算法简介
二、算法实现思路
三、模板题代码实现
四、参考文章
一、算法简介
Aho-Corasick automaton，该算法在1975年产生于贝尔实验室， 是著名的多模匹配算法。 要学会AC自动机，我们必须知道什么是Trie，也就是字典树。 Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树 的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字 符串），所以经常被搜索引擎系统用于文本词频统计。
——百度百科-AC自动机
太懒了
二、算法实现思路
-
板子题：P3808
给定
-
算法的构成：
复杂来说，AC自动机是以TRIE的结构为基础，结合KMP的思想建立的。
简单来说，AC_automaton = KMP+TRIE
其实AC自动机的结构非常清晰：一棵字典树 + 一个fail数组，就构成了它的全部。
-
字典树：
字典树又称Trie树，是一种用于保存多个字符串的树形结构。实现很简单，不在此赘述。具体可参照百度百科-字典树。
-
fail数组：
这个数组与KMP算法中的next数组都是基于同一个思想：用于在失配时跳转。不同的是，next数组所需的是最长相等前后缀，而fail数组只需要最长后缀即可。具体一点说，对于一个字典树上的节点
-
-
不存在其他节点
v ,使得v 对应的字符串也是B 的后缀，并且这个字符串比B 长（即这棵树上B 是A 的最长后缀）; -
ps. fail数组的作用其实也相当于一堆指针。为了方便，下文有些地方会将其改称为fail指针。
-
fail数组的求法：
BFS + 递推。
我们可以先写出下列伪代码，理清BFS的大致框架：
建立队列q；
初始化fail数组所有元素为0；
将根节点所有儿子入队；
（为什么不直接将根节点入队？显然所有根节点的儿子的fail指针都指向根，而根节点编号为0，如果先将根节点入队，遍历完它的所有儿子后fail数组不会发生变化，不如直接将根节点的所有儿子入队）
当q不为空时：
取出队首u；
遍历所有字符：
记当前遍历到的字符为i；
如果i是u和u的一个儿子v之间的边：
给fail[v]赋值；
将v入队；剩下要做的，就是思考如何利用递推求得伪代码中的
考虑字典树中的一个节点
前文已经说明， （想一想，为什么）。所以，如果节点
如果
以上，我们就通过递推完成了fail数组的构建。
说了那么多，上代码加深一下印象：
int fail[maxN],trie[maxN][26];
void get_fail(){
queue<int> q;
for(int i=0;i<26;i++) if(trie[0][i]) q.push(trie[0][i]);
while(!q.empty()){
int now=q.front(); q.pop();
for(int i=0;i<26;i++){
int &son=trie[now][i];//用传引用方式简化代码
if(son){
fail[son]=trie[fail[now]][i];//？？Q1
q.push(son);
}
else son=trie[fail[now]][i];//？？Q2
}
}
}小朋友你是否有很多问号？
上面的代码中，我们发现了两个之前没提到的问题：
Q1 为何此处不是按常理的上溯，而是直接赋值？
Q2 为何此处还要给不存在的儿子赋值？
其实，这两个问题问到了AC自动机的精髓，也是AC自动机优化时间复杂度的重要步骤。
Q1和Q2对应的代码其实是相辅相成的。它们将一棵字典树变成了一个字典图。（我也不知道字典图是什么，反正就叫这个名字这个字典图在查询时也能发挥很大作用。
Q2对应的代码类似并查集中的路径压缩，本来从节点
-
查询：
查询比起求fail数组就显得简单很多了，只有三个点需要注意：
-
要将访问过后的点打上标记，防止重复计算；
-
每次访问过一个点后要一直跳fail指针，将所有满足的点都统计到；
-
不必繁琐地写回溯的代码，因为字典图已经能实现自动跳转。
另有一些细节问题详见代码注释。
code:
//假设fail数组已经求得
int sum=0;//sum是匹配成功的模式串总数
void query(string s){
int pos=0,len=s.length();
for(int i=0;i<len;i++){
int ch=s[i]-'a';
pos=trie[pos][ch];//字典图实现自动跳转，如果还不懂为什么可以手动模拟一下
for(int j=pos;j && End[j]!=-1;j=fail[j]){
sum+=End[j];//这里End[j]存储的是以节点j为结尾的字符串有多少个，可以处理含有相同模式串的多模式匹配问题
End[j]=-1;//打上标记
}
}
}三、模板题代码实现
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
using namespace std;
const int maxN=1e6+5;
int n,tot,sum,fail[maxN],End[maxN],trie[maxN][26];
string str,txt;
void ins(string s){
int pos=0,len=s.length();
for(int i=0;i<len;i++){
int ch=s[i]-'a';
if(trie[pos][ch]) pos=trie[pos][ch];
else trie[pos][ch]=++tot,pos=tot;
if(i==len-1) End[pos]++;
}
}
void get_fail(){
queue<int> q;
for(int i=0;i<26;i++) if(trie[0][i]) q.push(trie[0][i]);
while(!q.empty()){
int now=q.front(); q.pop();
for(int i=0;i<26;i++){
int &son=trie[now][i];
if(son){
fail[son]=trie[fail[now]][i];
q.push(son);
}
else son=trie[fail[now]][i];
}
}
}
void query(string s){
get_fail();
int pos=0,len=s.length();
for(int i=0;i<len;i++){
int ch=s[i]-'a';
pos=trie[pos][ch];
for(int j=pos;j && End[j]!=-1;j=fail[j]){//访问到了根节点或已访问过的点就结束跳转
sum+=End[j];
End[j]=-1;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;i++){
cin>>str;
ins(str);
}
cin>>txt;
query(txt);
cout<<sum;
return 0;
}AC自动机顾名思义就是这份代码交到哪里都能AC，所以快来ctj吧
四、参考文章
-
强势 图解 AC自动机（保证您一次就能学会！）
-
ac自动机最详细的讲解，让你一次学会ac自动机。【转载】
-
AC自动机 算法详解(图解)及模板