AC自动机
AC自动机能解决单个母串，多个子串的问题，例如某一个子串出现了多少次，一共出现了几个子串等等.
网上常常说AC自动机是Kmp+字典树
简单来说为三步
1.建立子串的字典树
2建立fail指针，从而添加失败路径
3.跑母串
看一下例题
洛谷AC自动机加强版
题目描述
有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1000010;
int trie[maxn][26];
int fail[maxn];
int sum[maxn];
char str1[200][100];
char str2[maxn];
int tot=0,eend[maxn],ans[200];
void init(void){
memset(trie,0,sizeof(trie));
memset(fail,0,sizeof(fail));
memset(sum,0,sizeof(sum));
memset(eend,0,sizeof(eend));
memset(ans,0,sizeof(ans));
tot=0;
}
void _insert(int a){
int p=0,k,len=strlen(str1[a]);
for(int i=0;i<len;i++){
k=str1[a][i]-'a';
if(!trie[p][k]) trie[p][k]=++tot;
p=trie[p][k];
}
sum[p]=1;
eend[p]=a;
}
void getfail(void){
queue<int>q;
for(int i=0;i<26;i++){
if(trie[0][i]){
fail[trie[0][i]]=0;
q.push(trie[0][i]);
}
}
while(q.size()){
int p;
int now=q.front();
q.pop();
for(int i=0;i<26;i++){
p=trie[now][i];
if(p) fail[p]=trie[fail[now]][i],q.push(p);
else trie[now][i]=trie[fail[now]][i];
}
}
}
void _search(){
int p=0,k,len=strlen(str2);
for(int i=0;i<len;i++){
k=str2[i]-'a';
p=trie[p][k];
for(int j=p;j;j=fail[j])
ans[eend[j]]+=sum[j];
}
return ;
}
int main(void){
int n;
while(scanf("%d",&n),n){
init();
for(int i=1;i<=n;i++){
scanf("%s",str1[i]);
_insert(i);
}
getfail();
scanf("%s",str2);
_search();
int maxx=-1;
for(int i=1;i<=n;i++)
maxx=max(maxx,ans[i]);
printf("%d\n",maxx);
for(int i=1;i<=n;i++){
if(ans[i]==maxx)
printf("%s\n",str1[i]);
}
}
return 0;
}
我们发现，其实这样写时间复杂度一样很高，有没有更好的方法去求呢？是有的，我们发现，我们以前都是将fail指针指出去，用后缀去匹配前缀，如果我们反向建边，入度为1，此时它就是一棵树，这样我们在查找的时候就不需要利用fail指针连跳，而是一个点直接就是他的子树和加上他自己，在树上跑一边dfs就行，再想，发现连dfs都不用跑，直接拓扑序就好了.
例题：洛谷（AC自动机二次加强版），这题题目和上题基本类似，但是用上题的方法肯定会T
题目：一个母串多个子串，求每个子串出现的次数
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=2000010;
int trie[maxn][26];
int fail[maxn];
int sum[maxn]; //第a个串最后一个字符对应的p
char str1[maxn];
char str2[maxn];
int tot=0;
int head[maxn],ver[maxn],nt[maxn];
int cnt=0;
int d[maxn];
void init(int n){
memset(trie,0,sizeof(trie));
memset(fail,0,sizeof(fail));
memset(sum,0,sizeof(sum));
memset(d,0,sizeof(d));
memset(head,0,sizeof(head));
tot=0;
cnt=0;
}
void _insert(int a){
int p=0,k,len=strlen(str1);
for(int i=0;i<len;i++){
k=str1[i]-'a';
if(!trie[p][k]) trie[p][k]=++tot;
p=trie[p][k];
}
sum[a]=p;
}
void getfail(void){
queue<int>q;
for(int i=0;i<26;i++){
if(trie[0][i]){
fail[trie[0][i]]=0;
q.push(trie[0][i]);
}
}
while(q.size()){
int p;
int now=q.front();
q.pop();
for(int i=0;i<26;i++){
p=trie[now][i];
if(p)
fail[p]=trie[fail[now]][i],q.push(p);
else trie[now][i]=trie[fail[now]][i];
}
}
}
void _search(void){
int p=0,k,len=strlen(str2);
for(int i=0;i<len;i++){
k=str2[i]-'a';
p=trie[p][k];
d[p]++;
}
return ;
}
void add(int x,int y){
ver[++cnt]=y,nt[cnt]=head[x],head[x]=cnt;
}
void DFS(int x){
for(int i=head[x];i;i=nt[i]){
DFS(ver[i]);
d[x]+=d[ver[i]];
}
return ;
}
int main(void){
int n;
scanf("%d",&n);
init(n);
for(int i=1;i<=n;i++){
scanf("%s",str1);
_insert(i);
}
getfail();
for(int i=1;i<=tot;i++)
add(fail[i],i);
scanf("%s",str2);
_search();
DFS(0);
for(int i=1;i<=n;i++)
printf("%d\n",d[sum[i]]);
return 0;
}
