input
n 1<=n<=150
word1
word2
...
wordn
1<=len(wirdi)<=70
s 1<=len(s)<=1000000
output
最多出现次数
出现最多的串，按输入顺序输出，可能出现相同串，也要输出
做法：用一个end数组记下每个串结尾的字符的下标，对应val为１，每次找到就将val++,然后找到最大的val,输出最大val对应的字符串
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
#define MAX 100000
#define LL long long
int cas=,T,n,sz,maxt,last[*],f[*],ch[*][],val[*],end[];
char s[MAX*+],word[][];
int idx(char&c) {return c-'a';}
void inittrie()
{
memset(ch[],,sizeof(ch[]));
sz=;
val[]=;
}
int insert(char*s)
{
int u=;
for(;*s;s++)
{
int c=idx(*s);
if(!ch[u][c])
{
memset(ch[sz],,sizeof(ch[]));
val[sz]=;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=;
return u;
}
void getFail()
{
std::queue<int>q;
f[]=;
for(int c=;c<;c++)
{
int u=ch[][c];
if(u) { f[u]=;q.push(u);last[u]=; }
}
while(!q.empty())
{
int r=q.front();q.pop();
for(int c=;c<;c++)
{
int u=ch[r][c];
if(!u){ ch[r][c]=ch[f[r]][c];continue; }
q.push(u);
int v=f[r];
while(v&&!ch[v][c]) v=f[v];
f[u]=ch[v][c];
last[u]=val[f[u]]?f[u]:last[f[u]];
}
}
}
void print(int j)
{
if(j)
{
if(val[j]) val[j]++;
print(last[j]);
}
}
void find(char*s)
{
int n=strlen(s);
int j=;
for(int i=;i<n;i++)
{
int c=idx(s[i]);
j=ch[j][c];
//printf("val[%d]=%d\n",j,val[j]);
//if(val[j]) val[j]++;
//else if(last[j]) val[last[j]]++;
if(val[j]) print(j);
else if(last[j]) print(last[j]);
}
}
int main()
{
//freopen("/home/user/桌面/in","r",stdin);
//scanf("%d\n",&T);
while(scanf("%d",&n)==&&n)
{
inittrie();
for(int i=;i<n;i++)
{
scanf("%s",word[i]);
end[i]=insert(word[i]);
}
maxt=-;
// for(int i=0;i<n;i++) printf("%d %d %s\n",end[i],val[end[i]],word[i]);
getFail();
scanf("%s",s);
find(s);
for(int i=;i<n;i++) maxt=std::max(maxt,val[end[i]]);
printf("%d\n",maxt-);
for(int i=;i<n;i++) if(val[end[i]]==maxt) puts(word[i]);
}
//printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
return ;
}