cjoj P1435 - 【模板题 USACO】AC自动机 && 洛谷 P3796 【模板】AC自动机（加强版）

又打了一遍AC自动稽。

海星。

好像是第一次打trie图，很久以前就听闻这个思想了。OrzＹＹＢ~

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#include<cstring>

#define il inline

#define rg register

#define vd void

#define sta static

typedef long long ll;

il int gi(){

	rg int x=0,f=1;rg char ch=getchar();

	while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();

	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

struct node{

	int son[26];

	int fail;

	int tot;

}S[150*75];int id;

char T[150][75],str[1000001];

int len[150];

il int newnode(){

	++id;

	for(rg int i=0;i<26;++i)S[id].son[i]=0;

	S[id].fail=S[id].tot=0;

	return id;

}

il vd insert(char*s,int n){

	int x=0;

	for(rg int i=0;i<n;++i)

		if(S[x].son[s[i]-'a'])x=S[x].son[s[i]-'a'];

		else x=S[x].son[s[i]-'a']=newnode();

}

int que[501],hd,tl;

il vd build_fail(){

	hd=tl=0;

	for(rg int i=0;i<26;++i)

		if(S[0].son[i]){

			int x=S[0].son[i];

			que[tl++]=x;

			S[x].fail=0;

		}

	while(hd^tl){

		int x=que[hd];

		for(rg int i=0;i<26;++i)

			if(S[x].son[i]){

				que[tl++]=S[x].son[i];

				S[S[x].son[i]].fail=S[S[x].fail].son[i];

			}else S[x].son[i]=S[S[x].fail].son[i];

		++hd;

	}

}

int main(){

#ifdef xzz

	freopen("3796.in","r",stdin);

	freopen("3796.out","w",stdout);

#endif

	while(1){

		int n=gi();if(!n)break;

		id=0;

		for(rg int i=0;i<26;++i)S[0].son[i]=0;

		S[0].fail=S[0].tot=0;

		for(rg int i=1;i<=n;++i)scanf("%s",T[i]+1),len[i]=strlen(T[i]+1),insert(T[i]+1,len[i]);

		build_fail();

		scanf("%s",str+1);

		int m=strlen(str+1);

		int x=0;

		for(rg int i=1;i<=m;++i)x=S[x].son[str[i]-'a'],++S[x].tot;

		for(rg int i=tl-1;i;--i){

			x=que[i];

			S[S[x].fail].tot+=S[x].tot;

		}

		static int ans[151];

		for(rg int i=1;i<=n;++i){

			int x=0;

			for(rg int j=1;j<=len[i];++j)x=S[x].son[T[i][j]-'a'];

			ans[i]=S[x].tot;

		}

		ans[0]=0;for(rg int i=1;i<=n;++i)ans[0]=std::max(ans[0],ans[i]);

		printf("%d\n",ans[0]);

		for(rg int i=1;i<=n;++i)if(ans[i]==ans[0])printf("%s\n",T[i]+1);

	}

	return 0;

}