AC自动机

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
#define LAXM 160
int n;
char a[MAXN],s[LAXM][80];
int tr[MAXN][26],fail[MAXN],tot;
int idx[MAXN],val[MAXN],cnt[LAXM];
void insert(char *s,int ls,int id)
{
	int p=0;
	for(int i=1;i<=ls;++i)
	{
		int c=s[i]-'a';
		if(!tr[p][c]) tr[p][c]=++tot;
		p=tr[p][c];
	} 
	idx[p]=id;
}
queue<int>q;
void build()
{
	for(int i=0;i<26;++i)
	{
		if(tr[0][i]) q.push(tr[0][i]);
	}
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=0;i<26;++i)
		{
			if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
			else tr[u][i]=tr[fail[u]][i];
		}
	}
}
int find(char *s,int ls)
{
	int p=0,res=0;
	for(int i=1;i<=ls;++i)
	{
		int c=s[i]-'a';
		p=tr[p][c];
		for(int j=p;j;j=fail[j])
		{
			++val[j];
		}
	}
	for(int i=0;i<=tot;++i)
	{
		if(idx[i]) res=max(res,val[i]),
		cnt[idx[i]]=val[i];
	}
	return res;
}
void into()
{
	memset(tr,0,sizeof(tr));
	memset(fail,0,sizeof(fail));
	memset(idx,0,sizeof(idx));
	memset(val,0,sizeof(val));
	memset(cnt,0,sizeof(cnt));
	tot=0;
}
int main()
{
	while(1)
	{
		scanf("%d",&n);
		if(n==0) break;
		into();
		for(int i=1;i<=n;++i)
		{
			scanf("%s",s[i]+1);
			int len=strlen(s[i]+1);
			insert(s[i],len,i);
		}
		build();
		scanf("%s",a+1);
		int len=strlen(a+1); 
		int ans=find(a,len);
		printf("%d\n",ans);
		for(int i=1;i<=n;++i)
		{
			if(cnt[i]==ans) printf("%s\n",s[i]+1);
		}
	}
	return 0;
}