记录编号	421198	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.127 s
提交时间	2017-07-06 11:58:03	内存使用	28.19 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct trie{
	int cnt,id;
	trie *fail,*ch[26];
	trie():fail(NULL),cnt(0),id(0){
		memset(ch,0,sizeof(ch));
	}
};
trie *root(new trie());
int n;
int m[11];
int size;
char key[11][51];
inline void insert(char *s,int x){
	int len(strlen(s));
	trie *now(root);
	for(int i=0;i<len;i++){
		int k(s[i]-'a');
		if(now->ch[k]==NULL){
			now->ch[k]=new trie();
			now->ch[k]->id=++size;
		}
		now=now->ch[k];
	}
	m[x]=now->id;
	now->cnt=x;
}
trie *zhan[1005];
int head(0),tail(-1);
inline void build(){
	for(int i=0;i<26;i++){
		if(root->ch[i]){
			root->ch[i]->fail=root;
			zhan[++tail]=root->ch[i];
		}
		else
			root->ch[i]=root;
	}
	while(head<=tail){
		trie *now(zhan[head++]);
		for(int i=0;i<26;i++){
			if(now->ch[i]!=NULL){
				now->ch[i]->fail=now->fail->ch[i];
				zhan[++tail]=now->ch[i];
			}
			else
				now->ch[i]=now->fail->ch[i];
		}
	}
}
int ans[1005];
inline void search(char *s){
	int len(strlen(s));
	trie *now(root);
	for(int i=0;i<len;i++){
		int k(s[i]-'a');
		now=now->ch[k];
		ans[now->id]++;
	}
	for(int i=tail;i>=0;i--){
		now=zhan[i];
		ans[now->fail->id]+=ans[now->id];
	}
	for(int i=1;i<=n;i++)
		printf("%s %d\n",key[i],ans[m[i]]);
}
char article[100000001];
inline int gg(){
	freopen("ACautomata.in","r",stdin);
	freopen("ACautomata.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",key[i]);
		insert(key[i],i);
	}
	build();
	scanf("%s",article);
	search(article);
	return 0;
}
int k(gg());
int main(){;}