（AC自动机）UVALive

每组数据，对模式串建立Trie树，为避免模式串重复的情况，用mao建立模式串与编号的对应关系。
对匹配串AC自动机处理，其中print改为更新出现次数。
最后找一下次数最大的输出即可。
  1 #include <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <queue>
  8 #include <set>
  9 #include <map>
 10 #include <list>
 11 #include <vector>
 12 #include <stack>
 13 #define mp make_pair
 14 #define MIN(a,b) (a>b?b:a)
 15 #define rank rankk
 16 //#define MAX(a,b) (a>b?a:b)
 17 typedef long long ll;
 18 typedef unsigned long long ull;
 19 const int MAX=1e6+5;
 20 const int INF=1e9+5;
 21 const int B=1024;//桶的大小
 22 const double M=4e18;
 23 using namespace std;
 24 const int MOD=1e9+7;
 25 typedef pair<int,int> pii;
 26 const double eps=0.000000001;
 27 
 28 map<string,int> re;
 29 const int SIGMA_SIZE=50;
 30 const int MAXNODE=11000;
 31 const int MAXS=160;
 32 /*
 33     由于失配过程比较复杂，要反复沿着失配边走，
 34     在实践中常常会把下述自动机改造一下，把所有不存在的边“补上”
 35     即把计算失配函数中的语句if(!u)continue;改成
 36     if(!u){ch[r][c]=ch[f[r]][c];continue;}
 37     这样，就完全不需要失配函数，而是对所有转移一视同仁
 38     即find函数中的while(j&&!ch[j][c])j=f[j] 可以直接删除
 39 
 40 */
 41 struct AhoCorasickAutomata
 42 {
 43     int ch[MAXNODE][SIGMA_SIZE];
 44     int f[MAXNODE];//fail函数
 45     int val[MAXNODE];//每个字符串的结尾结点都有非0的val
 46     int last[MAXNODE];//输出链表的下一个单词结点
 47     int num;//trie树编号（亦为包含根结点的当前size）
 48     int cnt[MAXNODE];
 49     //初始化
 50     void init()
 51     {
 52         num=1;
 53         memset(ch[0],0,sizeof(ch[0]));
 54         re.clear();
 55         memset(cnt,0,sizeof(cnt));
 56     }
 57     //返回字符对应编号
 58     int idx(char c)
 59     {
 60         return c-'a';
 61     }
 62     //插入权值为v的字符串
 63     void insert(char *s,int v)
 64     {
 65         int u=0,n=strlen(s);
 66         for(int i=0;i<n;i++)
 67         {
 68             int c=idx(s[i]);
 69             if(!ch[u][c])
 70             {
 71                 memset(ch[num],0,sizeof(ch[num]));
 72                 val[num]=0;
 73                 ch[u][c]=num++;
 74             }
 75             u=ch[u][c];
 76         }
 77         val[u]=v;
 78         re[s]=v;
 79     }
 80     //递归打印以结点j结尾的所有字符串
 81     void print(int j)
 82     {
 83         if(j)
 84         {
 85             ++cnt[val[j]];
 86             print(last[j]);
 87 //            printf("%d %d
",j,val[j]);
 88 //            print(last[j]);
 89         }
 90     }
 91     //计算fail函数
 92     void getFail()
 93     {
 94         queue <int> que;
 95         f[0]=0;
 96         for(int c=0;c<SIGMA_SIZE;c++)
 97         {
 98             int u=ch[0][c];
 99             if(u)
100             {
101                 f[u]=0;que.push(u);last[u]=0;
102             }
103         }
104         while(!que.empty())
105         {
106             int r=que.front();que.pop();
107             for(int c=0;c<SIGMA_SIZE;c++)
108             {
109                 int u=ch[r][c];
110                 if(!u)
111                     continue;
112                 que.push(u);
113                 int v=f[r];
114                 while(v&&!ch[v][c])//类似kmp的过程
115                     v=f[v];
116                 f[u]=ch[v][c];
117                 last[u]=val[f[u]]?f[u]:last[f[u]];
118             }
119         }
120     }
121     //在T中中模板
122     int find(char *T)
123     {
124         int n=strlen(T);
125         int u=0;//当前结点编号,初始为根结点
126         for(int i=0;i<n;i++)//文本串当前指针
127         {
128             int c=idx(T[i]);
129             while(u&&!ch[u][c])//顺着失配指针走，直到可以匹配或回到根节点
130                 u=f[u];
131             u=ch[u][c];
132             if(val[u])//当前位置恰好是某个模式串第一次出现
133                 print(u);
134             else if(last[u])//当前位置作为后缀，与某前缀与模式串相同
135                 print(last[u]);
136         }
137     }
138 
139 };
140 int n;
141 char tem[151][80];
142 char temp[MAX];
143 AhoCorasickAutomata ac;
144 int main()
145 {
146     while(scanf("%d",&n)&&n)
147     {
148         ac.init();
149         for(int i=1;i<=n;i++)
150         {
151             scanf("%s",tem[i]);
152             ac.insert(tem[i],i);
153         }
154         ac.getFail();
155         scanf("%s",temp);
156         ac.find(temp);
157         int an=-1;
158         for(int i=1;i<=n;i++)
159         {
160             if(ac.cnt[i]>an)
161             {
162                 an=ac.cnt[i];
163             }
164         }
165         printf("%d
",an);
166         for(int i=1;i<=n;i++)
167         {
168             if(ac.cnt[re[string(tem[i])]]==an)
169                {
170                    printf("%s
",tem[i]);
171                }
172         }
173     }
174     return 0;
175 }