记录编号	284137	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.155 s
提交时间	2016-07-17 06:35:03	内存使用	96.24 MiB

#include<stdio.h>
int n,id[110],cnt,son[5010][26];
char s[110][55];
char ch[100000010];
void build(){
	for(int i=0,j,now;i<n;++i){
		scanf("%s",s[i]);
		for(j=now=0;s[i][j];++j){
			if(!son[now][s[i][j]-97])son[now][s[i][j]-97]=++cnt;
			now=son[now][s[i][j]-97];
		}
		id[i]=now;
	}
}
int l,r,q[5010],fail[5010];
void get_fail(){
	q[l=r=0]=0;
	for(int x;l<=r;++l){
		x=q[l];
		for(int i=0;i<26;++i)if(son[x][i]){
			if(x)fail[son[x][i]]=son[fail[x]][i];
			q[++r]=son[x][i];
		}else son[x][i]=son[fail[x]][i];
	}
}
int num[5010],ans[5010];
int main(){
	freopen("ACautomata.in","r",stdin);
	freopen("ACautomata.out","w",stdout);
	scanf("%d",&n);
	build();
	get_fail();
	scanf("%s",ch);
	for(int i=0,now=0;ch[i];++i){
		now=son[now][ch[i]-97];
		++num[now];
	}
	for(int i=cnt;i;--i)
		for(int now=i,j=num[now];now;now=fail[now])
			ans[now]+=j;
	for(int i=0;i<n;++i)
		printf("%s %d\n",s[i],ans[id[i]]);
}