记录编号	414515	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	0.518 s
提交时间	2017-06-14 15:14:34	内存使用	95.82 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 1005
using namespace std;
char s[15][55],ss[100000010];
int n,len,tot,match[15],h,t,sum[N];
struct Trie{
	int id,pp;
	Trie *ch[30],*fail;
	Trie(){
		memset(ch,0,sizeof(ch));
		fail=NULL; id=pp=0;
	}
}node[N],*root,*q[N];
Trie *newnode(){
	tot++;
	memset(node[tot].ch,0,sizeof node[tot].ch);
	node[tot].id=node[tot].pp=0; node[tot].fail=NULL;
	return &node[tot];
}
void insert(char *s,int x){
	len=strlen(s);
	Trie *now=root;
	for(int i=0;i<len;i++)
	{
		int st=s[i]-'a';
		if(now->ch[st]==NULL){
		  now->ch[st]=newnode();
		  now->ch[st]->id=tot;
		}
  		now=now->ch[st];  
	}
	match[x]=now->id;
	now->pp=x;
}
void getfail(){
	root->fail=NULL;
	h=0,t=-1;
	for(int i=0;i<26;i++){
	  if(root->ch[i]){
	  	root->ch[i]->fail=root;
	    q[++t]=root->ch[i];
	  }
	  else root->ch[i]=root;
	}
    while(h<=t){
   	  Trie *now=q[h++];
	  for(int i=0;i<26;i++){
	    if(now->ch[i]!=NULL){
	    	now->ch[i]->fail=now->fail->ch[i];
	    	q[++t]=now->ch[i];
		}
		else now->ch[i]=now->fail->ch[i];
	  }
	}
}
void read(){
	memset(ss,0,sizeof(ss));
	len=0;
	char cc=getchar();
	while(cc<'a'||cc>'z') cc=getchar();
	while(cc>='a'&&cc<='z'){
        ss[len++]=cc;
	    cc=getchar();
	}
}
void work(){
	memset(sum,0,sizeof(sum));
	Trie *now=root;
	for(int i=0;i<len;i++){
		int st=ss[i]-'a';
		now=now->ch[st];
		sum[now->id]++;
	}
	for(int i=t;i>=0;i--){
		now=q[i];
		sum[now->fail->id]+=sum[now->id];
	}
	for(int i=1;i<=n;i++)
		printf("%s %d\n",s[i],sum[match[i]]);
}
int main()
{
	//freopen("1.txt","r",stdin);
	freopen("ACautomata.in","r",stdin);
	freopen("ACautomata.out","w",stdout);
	root=newnode();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s[i]);
		insert(s[i],i);
		//printf("%s  %d\n",s[i],i);
	}
	getfail();
	read();
	work();
}