ustc.rar_ustc

#include<cstdio> #include<cstring> using namespace std; char t[155][75],s[1000005],c; int slen[155]; int time[155],mx,n,len,q[155],tail,num; void kmp(int a){ int i,j; int r[80]; for (i=1,j=r[0]=-1;i<slen[a];i++){ while(j>=0 && t[a][i-1]!= t[a][j]) j=r[j]; r[i]=++j; } for (i=0,j=0;i<len;i++,j++){ while(j>=0 && s[i]!=t[a][j]) j=r[j] ; if (j==slen[a]-1) {num++;i=i-slen[a]+1;j=-1;} } } void solve(){ int i; mx=0; tail=0; for (i=1;i<=n;i++){ num=0; kmp(i); if (num>mx){ mx=num; tail=0; q[tail++]=i; } else if (num==mx){ q[tail++]=i; } } } int main(){ int i; while(1){ scanf("%d",&n); if (n==0) break; for (i=1;i<=n;i++) {scanf("%s",t[i]);slen[i]=strlen(t[i]);} scanf("%c",&c); len=0; while(1){ scanf("%c",&c); if (c=='\n') break; s[len++]=c; } solve(); printf("%d\n",mx); for (i=0;i<tail;i++){ printf("%s\n",t[q[i]]); } } return 0; }