「模板」AC自动机（ACAM）-白红宇

「模板」AC自动机（ACAM）

阅读量：4494 次

发布时间：2019-06-08

本文共 2353 字，大约阅读时间需要 7 分钟。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN=160,MAXM=11000,MAXL=1000010;char str[MAXN][80],p[MAXL];int n;class ACAM{    public:        void Init(void)        {            tot=0;            memset(cnt,0,sizeof cnt);            memset(s,0,sizeof s);        }        void Insert(char *str,int k)        {            int x=0;            for(int i=0,t;str[i];++i)            {                if(!s[x].c[t=num(str[i])])                    s[x].c[t]=++tot;                x=s[x].c[t];            }            s[x].index=k;        }        void GetFail(void)        {            queue
        
          q;            for(int i=1,t;i<=26;++i)                if(t=s[0].c[i])                {                    s[t].fail=0;                    q.push(t);                }            while(!q.empty())            {                int x=q.front();                q.pop();                for(int i=1,t,f;i<=26;++i)                    if(t=s[x].c[i])                    {                        f=s[t].fail=s[s[x].fail].c[i];                        s[t].lst=s[f].index?f:s[f].lst;                        q.push(t);                    }                    else                        s[x].c[i]=s[s[x].fail].c[i];            }        }        void Search(char *p)        {            int x=0,ans=0;            for(int i=0;p[i];++i)            {                if(s[x=s[x].c[num(p[i])]].index)                    ++cnt[s[x].index];                for(int j=s[x].lst;j;j=s[j].lst)                    ++cnt[s[j].index];            }            for(int i=1;i<=n;++i)                ans=max(ans,cnt[i]);            printf("%d\n",ans);            for(int i=1;i<=n;++i)                if(cnt[i]==ans)                    printf("%s\n",str[i]);        }    private:        int tot,cnt[MAXN];        struct node        {            int index,fail,lst,c[27];        }s[MAXM];        int num(char c)        {            return c-'a'+1;        }}AC;int main(int argc,char *argv[]){    while(scanf("%d",&n) && n)    {        AC.Init();        for(int i=1;i<=n;++i)        {            scanf("%s",str[i]);            AC.Insert(str[i],i);        }        AC.GetFail();        scanf("%s",p);        AC.Search(p);    }    return 0;}