记录编号	191101	评测结果	AAAAAAT
题目名称	AC自动机	最终得分	85
用户昵称	stdafx.h	是否通过	未通过
代码语言	C++	运行时间	1.092 s
提交时间	2015-10-06 16:17:58	内存使用	19.43 MiB

//algorithm::ac_automata

#define MAXN 1010UL
#define MAXL 51UL
#define MAXE 20000010UL
#define MAXS 26UL

#include <cstdio>
#include <cstring>
#include <queue>

struct Node{
	int id;
	Node *ch[MAXS],*fail;
	Node(){id=0;for(int i=0;i<MAXS;i++) ch[i]=NULL;fail=NULL;return;}
};

Node *root=new Node();

char str[MAXN][MAXL],s[MAXE];
int n,t,Ans[MAXN],len;
std::queue<Node*> que;

inline void Add_Trie(char *p,int id){
	Node *r=root;
	for(;*p;r=r->ch[t],p++){
		t=*p-'a';
		if(!r->ch[t]) r->ch[t]=new Node();	
	}
	r->id=id;return;
}

int main(){
	freopen("ACautomata.in","r",stdin);freopen("ACautomata.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%s",str[i]),Add_Trie(str[i],i);
	que.push(root);
	while(!que.empty()){
		Node *tmp=que.front();que.pop();
		for(t=0;t<MAXS;t++){
			if(tmp->ch[t]){
				Node *p=tmp->fail;
				while(p&&(!p->ch[t])) p=p->fail;
				if(!p) tmp->ch[t]->fail=root;
				else tmp->ch[t]->fail=p->ch[t];
				que.push(tmp->ch[t]);
			}
		}
	}
	scanf("%s",s);len=strlen(s);Node *tmp=root;
	for(int i=0;i<len;i++){
		t=s[i]-'a';
		while(tmp&&!tmp->ch[t]) tmp=tmp->fail;
		if(!tmp) tmp=root;
		else tmp=tmp->ch[t];
		Node *p=tmp;
		while(p) Ans[p->id]++,p=p->fail;
	}
	for(int i=1;i<=n;i++){
		printf("%s %d\n",str[i],Ans[i]);
	}
	return 0;
}