ac自动机模板

ac自动机是多模式字符串匹配，建立在字典树的基础上。

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10005;
const int cs=26;
struct AC
{
    int next[maxn][cs],val[maxn];
    int id;
    int fail[maxn],last[maxn];
    void init(){ memset(next[0],0,sizeof(next[0])); id=0; }//刚开始只初始化根节点
    int GetId(char c){ return c-'a'; }
    void Insert(char *S,int I) //字典树插入字符串
    {
        int s,be=0;
        for(int i=0;S[i]!='';i++)
        {
            s=GetId(S[i]);
            if(next[be][s]==0)
            {
                next[be][s]=++id; //增加新节点
                val[id]=0;      //置0
                memset(next[id],0,sizeof(next[id])); //清空
            }
            be=next[be][s];
        }
        val[be]=I;//保存信息
    }
    void GetFail() //找失配指针
    {
        queue<int> que;
        fail[0]=0;
        for(int i=0;i<cs;i++)
        {
            int u=next[0][i];
            fail[u]=last[u]=0;
            if(u) que.push(u);
        }
        while(!que.empty())
        {
            int x=que.front(); que.pop();
            for(int i=0;i<cs;i++)
            {
                int u=next[x][i];
                if(!u){ next[x][i]=next[fail[x]][i]; continue; }
                que.push(u);
                int v=fail[x];
                while(v&&!next[v][i]) v=fail[v];
                fail[u]=next[v][i];
                last[u]=val[fail[u]]?fail[u]:last[fail[u]];
            }
        }
    }
    void Print(int i,int j)
    {
        if(!j) return;
        printf("%d: %d
",i,val[j]);
        Print(i,last[j]);
    }
    void Find(char *T)  //匹配
    {
        int L=strlen(T);
        int j=0,s;
        for(int i=0;i<L;i++)
        {
            s=GetId(T[i]);
            j=next[j][s];
            if(val[j]) Print(i,j);
            else if(last[j]) Print(i,j);
        }
    }
}ac;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ac.init();
        int N;
        scanf("%d",&N);
        char mom[50],son[10][20];
        scanf("%s",mom);
        for(int i=1;i<=N;i++)
        {
            scanf("%s",son[i]);
            ac.Insert(son[i],i);
        }
        ac.GetFail();
        ac.Find(mom);
    }
    return 0;
}