【LA4670-Dominating Patterns】AC自动机

http://acm.hust.edu.cn/vjudge/problem/19224

题意：给定n个单词，一个字符串，问哪些单词在字符串中出现的次数最多。单词aba，文本ababa，则aba出现了2次。

题解：每找到一个记得要顺着fail找到所有单词。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<queue>

 using namespace std;

 const int N=,L=;

 char s[L],ss[N][];

 int cnt[N];

 int num,mx,n;

 struct node{

     int son[];

     int id,fail;

 }a[N*];

 queue<int> q;

 int maxx(int x,int y){return x>y ? x:y;}

 void clear(int x)

 {

     a[x].id=a[x].fail=;

     memset(a[x].son,,sizeof(a[x].son));

 }

 void trie(char *c,int id)

 {

     int l=strlen(c);

     int x=;

     for(int i=;i<l;i++)

     {

         int t=c[i]-'a'+;

         if(!a[x].son[t])

         {

             num++;

             clear(num);

             a[x].son[t]=num;

         }

         x=a[x].son[t];

     }

     a[x].id=id;

 }

 void buildAC()

 {

     while(!q.empty()) q.pop();

     for(int i=;i<=;i++)

         if(a[].son[i]) q.push(a[].son[i]);

     while(!q.empty())

     {

         int x=q.front();q.pop();

         int fail=a[x].fail;

         for(int i=;i<=;i++)

         {

             int y=a[x].son[i];

             if(y)

             {

                 a[y].fail=a[fail].son[i];

                 q.push(y);

             }

             else a[x].son[i]=a[fail].son[i];

         }

     }

 }

 void find(char *c)

 {

     int l=strlen(c);

     int x=;

     for(int i=;i<l;i++)

     {

         int t=c[i]-'a'+;

         if(!a[x].son[t]) x=;

         else x=a[x].son[t];

         int p=x;

         while(p)

         {

             if(a[p].id) cnt[a[p].id]++;

             p=a[p].fail;

         }

     }

 }

 int main()

 {

     freopen("a.in","r",stdin);

     freopen("a.out","w",stdout);

     while()

     {

         scanf("%d",&n);

         if(!n) return ;

         num=mx=;

         clear();

         memset(cnt,,sizeof(cnt));

         for(int i=;i<=n;i++)

         {

             scanf("%s",ss[i]);

             trie(ss[i],i);

         }

         buildAC();

         scanf("%s",s);

         find(s);

         for(int i=;i<=n;i++) mx=maxx(mx,cnt[i]);

         printf("%d\n",mx);

         for(int i=;i<=n;i++)

         {

             if(mx==cnt[i]) printf("%s\n",ss[i]);

         }

     }

     return ;

 }