记录编号	162867	评测结果	AAAAAAT
题目名称	AC自动机	最终得分	85
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	1.100 s
提交时间	2015-05-21 09:28:03	内存使用	19.43 MiB

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

using namespace std;

char str[1010][51],S[20000010];
int ansv[1010],n;

struct node{
	node *ch[26],*fail;
	int id;
}*root;

void addin(char *c,int id){
	node *p=root;
	while(*c!='\0'){
		int t=*c-'a';
		if(!p->ch[t]) p->ch[t]=new node();
		p=p->ch[t];
		c++;
	}
	p->id=id;
}

queue<node*> q;

int main(){
	freopen("ACautomata.in","r",stdin);
	freopen("ACautomata.out","w",stdout);
	scanf("%d",&n);
	root=new node();
	for(int i=1;i<=n;i++){
		scanf("%s",str[i]);
		addin(str[i],i);
	}
	q.push(root);
	while(!q.empty()){
		node* tmp=q.front(); q.pop();
		for(int t=0;t<26;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];
				q.push(tmp->ch[t]);
			}
	}
	scanf("%s",S);
	int len=strlen(S);
	node* tmp=root;
	for(int i=0;i<len;i++){
		int 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){
			if(p->id) ansv[p->id]++;
			p=p->fail;
		}
	}
	for(int i=1;i<=n;i++){
		printf("%s %d\n",str[i],ansv[i]);
	}
	return 0;
}