=====AC自动机=====

====引入====

$AC$ 自动机是一种多模式串匹配算法，一般用于解决对于在文本串中匹配一系列模式串（例：给一个文本串和一系列模式串，问模式串在文本串中一共出现了多少次）

====构造====

具体的构造方法我们可以参考 $KMP$，在每次匹配失败了之后，则需要从 $i$ 回到 $fail(i)$，即 $fail(i)$ 位置的前缀的是 $i$ 这个位置的前缀的后缀。

而 $AC$ 自动机则是在 $trie$ 上实现这样的操作。

{{:2020-2021:teams:hotpot:ac1.png?400|}}

如图所示

设 $i$ 的父亲为 $i'$，指向$i$点的边上的字母为$c$

显然，当 $fail(i')$ 有字母 $c$的出边时，该出边的指向的点即为 $fail(i)$。（图中 $fail(7)=1,fail(8)=2$）

否则，我们就应当沿着 $fail$ 函数一直向上寻找，直到找到为止，如果找不到一个符合条件的点，则 $fail(i)$ 为根。（图中fail(3)=0）

====匹配====

有了之前的构造之后我们的匹配较为简单，设当前在$i$点，每次新加入字符$c$,都检查$i$点有没有$c$的出边，如果有，则转移到该点，否则沿着$fail$去寻找这样的点（没有就会回到根结点）

如果到了一个单词结点上，则代表该单词被匹配了（可能会有$i$点不是单词但$fail(i)$是单词的情况）。

如下图 3 到 1 的情况。

{{:2020-2021:teams:hotpot:ac2.png?400|}}

为了解决此类问题，我们又可以引入后缀链接，$nxt(i)$ 表示从$i$沿着失配边转移，能够到达的第一个单词结点。

后缀链接可以在失配指针之后求出，如果 $fail(i)$ 为单词结点，则 $nxt(i)=fail(i)$,否则 $nxt(i)=nxt(fail(i))$

====优化====

由于每次失配时需要用到失配指针，每次加入字符时经过节点数不确定，复杂度可能退化，但对于一个状态，添加一个字符后，转移到的状态是确定的，这也意味着我们可以预处理每一个状态可能装一道的所有状态。

对于节点 $i$ ,如果它有字符 $c$的出边,则加入 $c$ 时，它可以直接转移到该边指向结点，否则应该转移到fail(i)加入对应字符转移到的点上，我们可以用递推的方式求出这些转移方式，加入这些边，得到$Trie$图

====模板题====

[[https://www.luogu.com.cn/problem/P3808|P3808 【模板】AC自动机（简单版）]]

ps:本题由于只记录串出现次数，可以通过标记来优化复杂度。

<code cpp>

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<map>
#include<stack>
#include<queue>
#include<complex>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=1000005;
char s[maxn];
int cnt,ch[maxn][26],Count[maxn],fail[maxn];
int nxt[maxn]; 
void Insert(){
	scanf("%s",s+1);
	int len=strlen(s+1);
	int rt=0;
	for(int i=1;i<=len;++i){
		int t=s[i]-'a';
		if(!ch[rt][t])ch[rt][t]=++cnt;
		rt=ch[rt][t];
	}
	++Count[rt];
}
queue<int> Q;
void Build_AC(){
	Q.push(0);
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<26;++i)
			if(ch[x][i]){
				if(x){
					fail[ch[x][i]]=ch[fail[x]][i];
					if(Count[ch[fail[x]][i]])nxt[ch[x][i]]=ch[fail[x]][i];
					else nxt[ch[x][i]]=nxt[ch[fail[x]][i]];
				}
				Q.push(ch[x][i]);
			}
			else ch[x][i]=ch[fail[x]][i];
	}
}
void Query(){
	scanf("%s",s+1);
	int len=strlen(s+1),rt=0;
	int ans=0;
	for(int i=1;i<=len;++i){
		int t=s[i]-'a';
		int a=ch[rt][t];
		while(a){
			if(Count[a]==-1)break;
			ans+=Count[a];
			Count[a]=-1;
			a=nxt[a];
		}
		rt=ch[rt][t];
	}	
	printf("%d",ans);
}
int n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)Insert();
	Build_AC();
	Query();
	return 0;
}	

</code>

[[https://www.luogu.com.cn/problem/P3796|P3796 【模板】AC自动机（加强版）]]

ps:本题按输入顺序输出所有出现次数最多的模式串。保留所有的串编号最后排序输出即可。

<code cpp>

#include<algorithm>
#include<stack>
#include<ctime>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int num=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){num=num*10+x-'0';x=getchar();}
	return num*f;
}
const int maxn=75*155;
char s[1000005];
bool str[maxn];
int ch[maxn][26],cnt,fail[maxn];
int prt[maxn],nxt[maxn];
int uni[maxn];
char alp[maxn];
int n; 
void Insert(int bh){
	scanf("%s",s);
	int len=strlen(s);
	int x=0;
	for(int i=0;i<len;++i){
		int t=s[i]-'a';
		if(!ch[x][t]){
			ch[x][t]=++cnt;
			prt[cnt]=x;alp[cnt]=s[i];
		}
		x=ch[x][t];
	}
	str[x]=true;uni[x]=bh;
}
queue<int> Q;
void build_ac(){
	Q.push(0);
	while(Q.size()){
		int x=Q.front();Q.pop();
		for(int i=0;i<26;++i)
			if(ch[x][i]){
				if(x){
					fail[ch[x][i]]=ch[fail[x]][i];
					if(str[ch[fail[x]][i]])nxt[ch[x][i]]=ch[fail[x]][i];
					else nxt[ch[x][i]]=nxt[ch[fail[x]][i]];
				}
				Q.push(ch[x][i]);
			}else ch[x][i]=ch[fail[x]][i];
	}
}
typedef pair<int,int> pr;
vector<pr> ans;
int MAX,num[maxn];
void qans(){
	scanf("%s",s);
	int len=strlen(s);
	int x=0;
	for(int i=0;i<len;++i){
		int t=s[i]-'a';
		int nw=ch[x][t];
		while(nw){
			if(str[nw])++num[nw];
			if(num[nw]==MAX)ans.push_back(pr(uni[nw],nw));
			if(num[nw]>MAX){
				MAX=num[nw];ans.clear();
				ans.push_back(pr(uni[nw],nw));
			}
			nw=nxt[nw];
		}
		x=ch[x][t];
	}
}
void write(int x){
	if(!x)return;
	write(prt[x]);
	printf("%c",alp[x]);
}
void Print(){
	printf("%d\n",MAX);
	sort(ans.begin(),ans.end());
	for(auto x:ans){
		write(x.second);
		puts("");
	}
}
void clear(){
	MAX=cnt=0;
	memset(str,0,sizeof str);
	memset(ch,0,sizeof ch);
	memset(fail,0,sizeof fail);
	memset(nxt,0,sizeof nxt);
	memset(num,0,sizeof num);
	memset(prt,0,sizeof prt);
	ans.clear();
}
int main(){
	while(true){
		clear();
		n=read();
		if(!n)break;
		for(int i=1;i<=n;++i)Insert(i);
		build_ac();
		//cout<<'a'<<endl;
		qans();
		Print();
	}
	return 0;
}

</code>

[[https://www.luogu.com.cn/problem/P5357|P5357 【模板】AC自动机（二次加强版）]]

ps:本题方法基本同上，记录一下每个串在trie上对应的点就可以了。

<code cpp>

#include<algorithm>
#include<stack>
#include<ctime>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int num=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){num=num*10+x-'0';x=getchar();}
	return num*f;
}
const int maxn=200005;
char s[maxn*10];
bool str[maxn];
int ch[maxn][26],cnt,fail[maxn];
int nxt[maxn],uni[maxn];
int n; 
void Insert(int bh){
	scanf("%s",s);
	int len=strlen(s);
	int x=0;
	for(int i=0;i<len;++i){
		int t=s[i]-'a';
		if(!ch[x][t])ch[x][t]=++cnt;
		x=ch[x][t];
	}
	str[x]=true;uni[bh]=x;
}
queue<int> Q;
void build_ac(){
	Q.push(0);
	while(Q.size()){
		int x=Q.front();Q.pop();
		for(int i=0;i<26;++i)
			if(ch[x][i]){
				if(x){
					fail[ch[x][i]]=ch[fail[x]][i];
					if(str[ch[fail[x]][i]])nxt[ch[x][i]]=ch[fail[x]][i];
					else nxt[ch[x][i]]=nxt[ch[fail[x]][i]];
				}
				Q.push(ch[x][i]);
			}else ch[x][i]=ch[fail[x]][i];
	}
}
int num[maxn];
void qans(){
	scanf("%s",s);
	int len=strlen(s);
	int x=0;
	for(int i=0;i<len;++i){
		int t=s[i]-'a';
		int nw=ch[x][t];
		while(nw){
			if(str[nw])++num[nw];
			nw=nxt[nw];
		}
		x=ch[x][t];
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)Insert(i);
	build_ac();
	qans(); 
	for(int i=1;i<=n;++i)printf("%d\n",num[uni[i]]);
	return 0;
}

</code>