#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <fstream>
using namespace std;
const int maxn = 2e4 + 10,maxm = 1e6 + 10;
char s[maxm],base[155][100];
int tot,nxt[maxn],to[maxn][26],q[maxn],idx,To[maxn],Nxt[maxn],h[maxn];
int cnt[maxn],match[maxn];
inline void add(int u,int v){
Nxt[++idx] = h[u],h[u] = idx ,To[idx] = v;
}
void dfs(int u){
for (int i = h[u],v = To[i] ; i ; i = Nxt[i],v = To[i])
dfs(v), cnt[u] += cnt[v];
}
int main(){
int n;
while (scanf("%d",&n),n){
memset(nxt,0,sizeof nxt);
memset(h,0,sizeof h);
memset(cnt,0,sizeof cnt);
memset(to,0,sizeof to);
idx = tot = 0;
for (int k = 1,t; k <= n ; ++k){
scanf("%s",base[k] + 1);
int p = 0;
for (int i = 1 ; base[k][i] ; ++i){
t = base[k][i] - 'a';
if (!to[p][t]) to[p][t] = ++tot;
p = to[p][t];
}
match[k] = p;
}
int l = 0,r = 0,front,p = 0,res = 0;
for (int i = 0 ; i < 26 ; ++i) if (to[p][i]) q[++r] = to[p][i];
while (l ^ r){
front = q[++l];
for (int i = 0,p ; i < 26 ; ++i){
p = to[front][i];
if (p) nxt[p] = to[nxt[front]][i],q[++r] = p;
else to[front][i] = to[nxt[front]][i];
}
}
scanf("%s",s + 1);
for (int i = 1,j = 0 ; s[i] ; ++i) j = to[j][s[i] -'a'],++cnt[j];
for (int i = 1 ; i <= tot ; ++i) add(nxt[i],i);
dfs(0);
for (int i = 1 ; i <= n ; ++i) res = max(res,cnt[match[i]]);
printf("%d\n",res);
for (int i = 1 ; i <= n ; ++i)
if (cnt[match[i]] == res)
printf("%s\n",base[i] + 1);
}
return 0;
}
P5357
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <fstream>
using namespace std;
const int maxn = 2e5 + 10,maxm = 2e6 + 10;
char s[maxm];
int tot,nxt[maxn],to[maxn][26],q[maxn],idx,To[maxn],Nxt[maxn],h[maxn];
int cnt[maxn],match[maxn];
inline void add(int u,int v){
Nxt[++idx] = h[u],h[u] = idx ,To[idx] = v;
}
void dfs(int u){
for (int i = h[u],v = To[i] ; i ; i = Nxt[i],v = To[i])
dfs(v), cnt[u] += cnt[v];
}
int main(){
int n;
scanf("%d",&n);
for (int k = 1,t; k <= n ; ++k){
scanf("%s",s + 1);
int p = 0;
for (int i = 1 ; s[i] ; ++i){
t = s[i] - 'a';
if (!to[p][t]) to[p][t] = ++tot;
p = to[p][t];
}
match[k] = p;
}
int l = 0,r = 0,front,p = 0,res = 0;
for (int i = 0 ; i < 26 ; ++i) if (to[p][i]) q[++r] = to[p][i];
while (l ^ r){
front = q[++l];
for (int i = 0,p ; i < 26 ; ++i){
p = to[front][i];
if (p) nxt[p] = to[nxt[front]][i],q[++r] = p;
else to[front][i] = to[nxt[front]][i];
}
}
scanf("%s",s + 1);
for (int i = 1,j = 0 ; s[i] ; ++i) j = to[j][s[i] -'a'],++cnt[j];
for (int i = 1 ; i <= tot ; ++i) add(nxt[i],i);
dfs(0);
for (int i = 1 ; i <= n ; ++i)
printf("%d\n",cnt[match[i]]);
return 0;
}