记录编号	398706	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.362 s
提交时间	2017-04-22 21:02:26	内存使用	107.89 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#define N 100000010
using namespace std;

int i,n,l,len;
int cnt[100010],val[100010],f[100010],z[100010],last[100010];
char c[30][55],s[N];

struct Tree{
	int val;
	int son[26];
}Trie[100010];

inline void Insert(int K){
	int i=0,t=0,x=0;
	for (i=0;i<=len;i++){
		x=c[K][i]-'a';
		if (!Trie[t].son[x])	t=Trie[t].son[x]=++l;
		else t=Trie[t].son[x];
	}
	val[t]=K;
}

inline void Make(){
	int head=0,tail=0,i=0,u=0,v=0,x=0;
	for (i=0;i<=25;i++)
	if (Trie[0].son[i])	z[++tail]=Trie[0].son[i];
	while (head!=tail){
		x=z[++head];
		for (i=0;i<26;i++){
			if (!Trie[x].son[i])	continue;
			u=Trie[x].son[i];
			z[++tail]=u;	v=f[x];
			while (v&&!Trie[v].son[i])	v=f[v];
			f[u]=Trie[v].son[i];
			last[u]=(val[f[u]])?f[u]:last[f[u]];
		}
	}
}

inline void AC(int x){if (x)	cnt[val[x]]++,AC(last[x]);}

inline void Work(){
	int i=0,u=0,j=0;
	scanf("%s",&s);	len=strlen(s)-1;
	for (i=0;i<=len;i++){
		u=s[i]-'a';
		while (j&&!Trie[j].son[u])	j=f[j];
		j=Trie[j].son[u];
		if (val[j])	AC(j);
		else if (last[j])	AC(last[j]);
	}
}

int main (){
	freopen("ACautomata.in","r",stdin);
	freopen("ACautomata.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++){
		scanf("%s",&c[i]);	len=strlen(c[i])-1;
		Insert(i);
	}
	Make();	Work();
	for (i=1;i<=n;i++)	printf("%s %d\n",c[i],cnt[i]);
	return 0;
}