#include <bits/stdc++.h>
using namespace std;
int t,n,trie[20010][26],ap[20010],pl[20010],fail[20010],que[20010],vis[20010],sum[20010][200],to[20010],th[20010],cnt=1;
char str[2000010][200];
void insert(char str[],int xu)
{
	int l=strlen(str),root=1;
	for(int i=0;i<l;i++)
	    {
	    	int id=str[i]-'a';
	    	if(!trie[root][id])trie[root][id]=++cnt;
	    	root=trie[root][id];
	    }
	ap[root]++;
	pl[root]=xu;
}

void build_ac()
{
	int head=0,tail=0;
	fail[0]=1;
	que[tail++]=1;
	while(head<tail)
	   {
	   	int now=que[head];
	   	for(int i=0;i<26;i++)
	   	    {
	   	       int p=fail[now];
	   	       if(!trie[now][i])continue;
               fail[trie[now][i]]=1;
               que[tail++]=trie[now][i];
			   while(p)
			      {
			      	if(trie[p][i])
			      	   {
					   fail[trie[now][i]]=trie[p][i];
					   break;
				       }
				    p=fail[p];
				  }	
			}
		head++;
	   }
}

void match_ac(char str[])
{
	int i=0,l=strlen(str),root=1;
	while(i<l)
	   {
	   	int id=str[i]-'a';
	   	while(!trie[root][id]&&root!=0)root=fail[root];
	   	int p=root;
	   	if(vis[trie[root][id]])
	   	   for(int i=1;i<=n;i++)to[i]+=sum[trie[root][id]][i];
	   	else
		   	{
		   	vis[trie[root][id]]=1;
		   	while(p!=0)to[pl[trie[p][id]]]+=ap[trie[p][id]],th[pl[trie[p][id]]]+=ap[trie[p][id]],p=fail[p];
			for(int i=1;i<=n;i++)sum[trie[root][id]][i]=th[i],th[i]=0;
		    }
	   	root=trie[root][id];
	   	if(root==0)root=1;
	   	i++;
	   }
}

int main()
{
	while(scanf("%d",&n)!=-1)
		{
		int maxn=0;
		if(n==0)return 0;
		for(int i=0;i<n;i++)
		    {
		    	scanf("%s",str[i]);
		    	insert(str[i],i+1);
			}
		scanf("%s",str[n]);
		build_ac();
		match_ac(str[n]);
		for(int i=1;i<=n;i++)maxn=max(to[i],maxn);
		printf("%d\n",maxn);
		for(int i=1;i<=n;i++)
		    if(to[i]==maxn)printf("%s\n",str[i-1]);
		for(int i=1;i<=cnt;i++)
		    {
		    ap[i]=pl[i]=fail[i]=vis[i]=0;
		    for(int j=0;j<26;j++)trie[i][j]=0;
		    for(int j=1;j<=n;j++)sum[i][j]=0;
		    }
		for(int i=1;i<=n;i++)to[i]=0;
		cnt=1;
	    }
	return 0;
}

开 O2 过了，但是希望能优化到不开 O2 能过。AC 自动机复杂度真是玄学。

提交记录