记录编号	381614	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	ONCE AGAIN	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2017-03-12 09:13:46	内存使用	9.88 MiB

#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
const int SIZEN = 510;
int ch[SIZEN][26]={0};
int fail[SIZEN]  ={0};
int q[SIZEN] = {0};
int match[SIZEN] = {0};
int node = 0,front = 0,back = -1;
char str[10000000];
char s[11][52];
inline void Insert(const int &I){
	int n = strlen(s[I]),now = 0;
	for(int i = 0;i < n;i++){
		int c = s[I][i]-'a';
		if(!ch[now][c])ch[now][c] = ++node;
		now = ch[now][c];
	}
	match[I] = now;
}
inline void getfail(){
	for(int i = 0;i < 26;i++)
		if(ch[0][i])q[++back] = ch[0][i];
	while(front <= back){
		int now = q[front++];
		for(int i = 0;i < 26;i++){
			int &u = ch[now][i];
			if(!u){u = ch[fail[now]][i];continue;}
			q[++back] = u;
			fail[u] = ch[fail[now]][i];
		}
	}
}
int sum[SIZEN] = {0},N;
inline void Match(){
	int n = strlen(str),c,now = 0;
	for(int i = 0;i < n;i++){
		c = str[i]-'a';
		now = ch[now][c];
		sum[now]++;
	}
	for(int i = back;i;i--){
		int x = q[i];
		sum[fail[x]] += sum[x];
	}
	for(int i = 1;i <= N;i++)
		printf("%s %d\n",s[i],sum[match[i]]);
}
int main(){
	freopen("ACautomata.in","r",stdin);
	freopen("ACautomata.out","w",stdout);
	scanf("%d",&N);
	for(int i = 1;i <= N;i++){
		scanf("%s",s[i]);
		Insert(i);
	}
	getfail();
	scanf("%s",str);
	Match();
	return 0;
}