题解 P3808 【【模板】AC自动机（简单版）】
hyfhaha
2019-05-09 15:13:51
# AC自动机详细讲解
AC自动机真是个好东西！之前学KMP被Next指针搞晕了，所以咕了许久都不敢开AC自动机，近期学完之后，发现AC自动机并不是很难，特别是对于KMP，个人感觉AC自动机比KMP要好理解一些，可能是因为我对树上的东西比较敏感（实际是因为我到现在都不会KMP）。
很多人都说AC自动机是在Trie树上作KMP，我不否认这一种观点，因为这确实是这样，不过对于刚开始学AC自动机的同学们就一些误导性的理解（至少对我是这样的）。KMP是建立在一个字符串上的，现在把KMP搬到了树上，不是很麻烦吗？实际上AC自动机只是有KMP的一种思想，实际上跟一个字符串的KMP有着很大的不同。
所以看这篇blog，请放下KMP，理解好Trie，再来学习。
## 前置技能
1.[Trie](https://www.luogu.org/blog/juruohyfhaha/trie-xue-xi-zong-jie)(很重要哦)
2.KMP的思想（懂思想就可以了，不需要很熟练）
# 问题描述
给定n个模式串和1个文本串，求有多少个模式串在文本串里**出现过**。
注意：是出现过，就是出现多次只算一次。
默认这里每一个人都已经会了Trie。
我们将n个模式串建成一颗Trie树，建的方式和建Trie完全一样。
假如我们现在有文本串ABCDBC。
我们用文本串在Trie上匹配，刚开始会经过2、3、4号点，发现到4，成功地匹配了一个模式串，然后就不能再继续匹配了，这时我们还要重新继续从根开始匹配吗？
不，这样的效率太慢了。这时我们就要借用KMP的思想，从Trie上的某个点继续开始匹配。
明显在这颗Trie上，我们可以继续从7号点开始匹配，然后匹配到8。
那么我们怎么确定从那个点开始匹配呢？我们称i匹配失败后继续从j开始匹配，j是i的Fail（失配指针）。
## 构建Fail指针
### Fail的含义
Fail指针的实质含义是什么呢？
如果一个点i的Fail指针指向j。那么root到j的字符串是root到i的字符串的一个后缀。
举个例子：（例子来自上面的图
```cpp
i:4 j:7
root到i的字符串是“ABC”
root到j的字符串是“BC”
“BC”是“ABC”的一个后缀
所以i的Fail指针指向j
```
同时我们发现，“C”也是“ABC”的一个后缀。
所以Fail指针指的j的深度要尽量大。
重申一下Fail指针的含义：((最长的(当前字符串的后缀))在Trie上可以查找到)的末尾编号。
感觉读起来挺绕口的蛤。感性理解一下就好了，没什么卵用的。知道Fail有什么用就行了。
### 求Fail
首先我们可以确定，每一个点i的Fail指针指向的点的深度一定是比i小的。（Fail指的是后缀啊）
第一层的Fail一定指的是root。（比深度1还浅的只有root了）
点i的父亲fa的Fail指针指的是fafail，那么如果fafail有和i值相同的儿子j，那么i的Fail就指向j。这里可能比较难理解一点，不过等会转换成代码就很好理解了。
由于我们在处理i的情况必须要先处理好fa的情况，所以求Fail我们使用BFS来实现。
实现的一些细节：
1、刚开始我们不是要初始化第一层的fail指针为root，其实我们可以建一个虚节点0号节点，将0的所有儿子指向root（编号为1)，然后root的fail指向0就OK了。效果是一样的。
2、如果不存在一个节点i，那么我们可以将那个节点设为fafail的值和i相同的儿子。保证存在性，就算是0也可以成功返回到根，因为0的所有儿子都是根。
3、无论fafail存不存在和i值相同的儿子j，我们都可以将i的fail指向j。因为在处理i的时候j已经处理好了，如果出现这种情况，j的值是第2种情况，也是有实际值的，所以没有问题。
4、实现时不记父亲，我们直接让父亲更新儿子
```cpp
void getFail(){
for(int i=0;i<26;i++)trie[0].son[i]=1; //初始化0的所有儿子都是1
q.push(1);trie[1].fail=0; //将根压入队列
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){ //遍历所有儿子
int v=trie[u].son[i]; //处理u的i儿子的fail，这样就可以不用记父亲了
int Fail=trie[u].fail; //就是fafail，trie[Fail].son[i]就是和v值相同的点
if(!v){trie[u].son[i]=trie[Fail].son[i];continue;} //不存在该节点，第二种情况
trie[v].fail=trie[Fail].son[i]; //第三种情况，直接指就可以了
q.push(v); //存在实节点才压入队列
}
}
}
```
# 查询
求出了Fail指针，查询就变得十分简单了。
为了避免重复计算，我们每经过一个点就打个标记为-1，下一次经过就不重复计算了。
同时，如果一个字符串匹配成功，那么他的Fail也肯定可以匹配成功（后缀嘛），于是我们就把Fail再统计答案，同样，Fail的Fail也可以匹配成功，以此类推……经过的点累加flag，标记为-1。
最后主要还是和Trie的查询是一样的。
```cpp
int query(char* s){
int u=1,ans=0,len=strlen(s);
for(int i=0;i<len;i++){
int v=s[i]-'a';
int k=trie[u].son[v]; //跳Fail
while(k>1&&trie[k].flag!=-1){ //经过就不统计了
ans+=trie[k].flag,trie[k].flag=-1; //累加上这个位置的模式串个数，标记 已 经过
k=trie[k].fail; //继续跳Fail
}
u=trie[u].son[v]; //到儿子那,存在性看上面的第二种情况
}
return ans;
}
```
# 代码
```cpp
#include<bits/stdc++.h>
#define maxn 1000001
using namespace std;
struct kkk{
int son[26],flag,fail;
}trie[maxn];
int n,cnt;
char s[1000001];
queue<int >q;
void insert(char* s){
int u=1,len=strlen(s);
for(int i=0;i<len;i++){
int v=s[i]-'a';
if(!trie[u].son[v])trie[u].son[v]=++cnt;
u=trie[u].son[v];
}
trie[u].flag++;
}
void getFail(){
for(int i=0;i<26;i++)trie[0].son[i]=1; //初始化0的所有儿子都是1
q.push(1);trie[1].fail=0; //将根压入队列
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){ //遍历所有儿子
int v=trie[u].son[i]; //处理u的i儿子的fail，这样就可以不用记父亲了
int Fail=trie[u].fail; //就是fafail，trie[Fail].son[i]就是和v值相同的点
if(!v){trie[u].son[i]=trie[Fail].son[i];continue;} //不存在该节点，第二种情况
trie[v].fail=trie[Fail].son[i]; //第三种情况，直接指就可以了
q.push(v); //存在实节点才压入队列
}
}
}
int query(char* s){
int u=1,ans=0,len=strlen(s);
for(int i=0;i<len;i++){
int v=s[i]-'a';
int k=trie[u].son[v]; //跳Fail
while(k>1&&trie[k].flag!=-1){ //经过就不统计了
ans+=trie[k].flag,trie[k].flag=-1; //累加上这个位置的模式串个数，标记已经过
k=trie[k].fail; //继续跳Fail
}
u=trie[u].son[v]; //到下一个儿子
}
return ans;
}
int main(){
cnt=1;scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
insert(s);
}
getFail();
scanf("%s",s);
printf("%d\n",query(s));
return 0;
}
```
希望学习更多AC自动机？看我的blog [这里](https://www.luogu.org/blog/juruohyfhaha/ac-zi-dong-ji)