记录编号	380047	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.374 s
提交时间	2017-03-08 10:11:38	内存使用	25.77 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=105,maxlen=51,SIZEN=maxn*maxlen*26;
int ch[SIZEN][26],last[SIZEN],v[SIZEN],fail[SIZEN];
int cct[maxn],cnt=0,q[SIZEN];char o[maxn][maxlen],cc[10000010];
void Add(char *s,int num){
	int p=0,x,i,len=strlen(s);
	for(i=0;i<len;i++){
		x=s[i]-'a';
		if(!ch[p][x])ch[p][x]=++cnt;
		p=ch[p][x];
	}
	v[p]=num;
}
void Dig(){
	int rt,i,s=1,t=0,x;
	for(i=0;i<26;i++)if(ch[0][i])q[++t]=ch[0][i];
	while(s<=t){
		rt=q[s++];
		for(i=0;i<26;i++){
			int &u=ch[rt][i];
			if(!u){u=ch[fail[rt]][i];continue;}
			q[++t]=u;x=fail[rt];
			while(x&&!ch[x][i])x=fail[x];
			x=ch[x][i];fail[u]=x;
			last[u]=v[x]?x:last[x];
		}
	}
}
void Add(int i){for(;i;i=last[i])cct[v[i]]++;}
void Run(char *s){
	int len=strlen(s),i,p=0;
	for(i=0;i<len;i++){
		p=ch[p][s[i]-'a'];
		if(v[p])Add(p);
		else if(last[p])Add(last[p]);
	}
}
int main(){
	freopen("ACautomata.in","r",stdin);freopen("ACautomata.out","w",stdout);
	int n,i;scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%s",o[i]),Add(o[i],i);
	scanf("%s",cc);Dig(),Run(cc);
	for(i=1;i<=n;i++)printf("%s %d\n",o[i],cct[i]);
}