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;
}