记录编号	200206	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	NVIDIA	是否通过	通过
代码语言	C++	运行时间	0.297 s
提交时间	2015-10-28 12:41:05	内存使用	30.55 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
int ch[100001][50],f[100001];
int last[100001],val[100001],cnt[1001];
int n,sz,q[100001],h,t,num;
char st[101][1001],ss[10000001];
int idx(char ch){return ch-'a';} 
void insert(char *s)
{
	int len,u(0);
	len=strlen(s);
	for (int i=0;i<len;i++){
	  	int c=idx(s[i]);
	  	if (!ch[u][c]){ch[u][c]=++sz;val[sz]=0;}
	  	u=ch[u][c];
	  }
	val[u]=++num;
} 
void prework()
{
   	int u,r,v;
   	h=t=0;f[0]=0;
   	for (int i=0;i<26;i++){
   	 	u=ch[0][i];
   	 	if (u){q[++t]=u;f[u]=last[u]=0;}
   	 }
   	while (h<t){
	  	r=q[++h];
        for (int i=0;i<26;i++){
          u=ch[r][i];
          if (!u){ch[r][i]=ch[f[r]][i];continue;}
          q[++t]=u;v=f[r];
          while(v&&!ch[v][i]) v=f[v];
           f[u]=ch[v][i];
           last[u]=val[f[u]]?f[u]:last[f[u]];
        }
	  } 
}
void print(int j)
{
	if (j){++cnt[val[j]];print(last[j]);}
} 
void find(char *s)
{
	int u,len,j(0);
	len=strlen(s);
	for (int i=0;i<len;i++)
	 {
	 	u=idx(s[i]);
	 	j=ch[j][u];
	 	if (val[j]) print(j);
	 	else if (last[j]) print(last[j]);
	 }
}
int main()
{
    freopen("ACautomata.in","r",stdin);
    freopen("ACautomata.out","w",stdout);
	scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%*c%s",&st[i]);
        insert(st[i]);
    }
    prework();
    scanf("%*c%s",&ss);
    find(ss);
    for (int i=1;i<=n;i++) printf("%s %d\n",st[i],cnt[i]);
}