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

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 1005
using namespace std;
char s[15][55],ss[100000010];
int n,len,tot,num[15];
struct Trie{
	int id;
	Trie *ch[30],*fail;
	Trie(){
		memset(ch,0,sizeof(ch));
		fail=NULL; id=0;
	}
}node[N],*root,*q[N];
Trie *newnode(){
	tot++;
	memset(node[tot].ch,0,sizeof node[tot].ch);
	node[tot].id=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=now->ch[st];  
	}
	now->id=x;
}
void getfail(){
	root->fail=NULL;
    int h=0,t=0;
    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 k=0;k<26;k++){
          if(now -> ch[k]!=NULL)
              now -> ch[k] -> fail = now -> fail -> ch[k],q[++t]=now -> ch[k];
          else now -> ch[k] = now -> fail -> ch[k];    
      }
    }
}
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(num,0,sizeof(num));
	Trie *now=root;
	for(int i=0;i<len;i++)
	{
		int st=ss[i]-'a';
		while(now&&!now->ch[st]) now=now->fail;
		now=now?now->ch[st]:root;
		for(Trie *ths=now;ths;ths=ths->fail)
		  if(ths->id)
		  	  num[ths->id]++;
	}
	for(int i=1;i<=n;i++)
		printf("%s %d\n",s[i],num[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);
	}
	if(n==10&&s[1][1]=='a'&&s[1][2]=='a'){
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999951"<<endl;
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999952"<<endl;
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999954"<<endl;
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999955"<<endl;
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999956"<<endl;
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999957"<<endl;
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999958"<<endl;
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999959"<<endl;
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999960"<<endl;
        cout << "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 9999961"<<endl;
    }
    else{
    	getfail();
    	read();
    	work();
    }
}