记录编号	381610	评测结果	AAAAAAA
题目名称	AC自动机	最终得分	100
用户昵称	河北交通广播992大师来了	是否通过	通过
代码语言	C++	运行时间	0.146 s
提交时间	2017-03-12 09:08:55	内存使用	27.35 MiB

#include <stdio.h>
#include <ctime>
#include <algorithm>
#include <cstring>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <cmath>
#include <vector>
#define Mem(a, b) memset(a, b, sizeof a)
#define Mcpy(a, b) memcpy(a, b, sizeof a)
#define RG register
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;
IL void qkin(RG int &res){
	RG int x,f=1; RG char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;}
IL void read(RG int &A){ qkin(A); }
IL void read(RG int &A,RG int &B){ qkin(A),qkin(B); }
IL void read(RG int &A,RG int &B,RG int &C){ qkin(A),qkin(B),qkin(C); }
#define Gets(s) scanf("%s", s+1);
const double INF = 1e60;
const int inf = 0x7f7f7f7f;
const double Pi = acos(-1);
const double eps = 1e-8;
const int maxn = 510;
char Word[11][55],P[100000010];
int cnt,ch[maxn][26],fail[maxn],last[maxn];
int num,ans[maxn],val[maxn],n;
bool ed[maxn];

void build(char *s){
	RG int m = strlen(s+1), p = 0;
	for(RG int i=1; i<=m; i++){
		RG int x = s[i] - 'a';
		if(!ch[p][x]) ch[p][x] = ++cnt;
		p = ch[p][x];
	}
	val[++num] = p;
	ed[p] = 1;
}
int q[maxn],h,r;
void getfail(){
	h = r = 0;
	RG int x;
	for(RG int i=0; i<26; i++) if(x = ch[0][i]) {
		q[r++] = x;
		last[x] = fail[x] = 0;
	}
	while(h != r){
		RG int k = q[h++];
		for(RG int i=0; i<26; i++){
			x = ch[k][i];
			if(!x){ ch[k][i] = ch[fail[k]][i]; continue; }
			q[r++] = x;
			RG int p = fail[k];
			while(p && !ch[p][i]) p = fail[p];
			p = ch[p][i];
			fail[x] = p;
			last[x] = ed[p] ? p : last[p];
		}
	}
}
void find(char *s){
	RG int m = strlen(s+1), p = 0;
	for(RG int i=1; i<=m; i++){
		RG int x = s[i] - 'a';
		p = ch[p][x];
		ans[p]++;
	}
	for(RG int i=r; i>=0; i--) ans[last[q[i]]] += ans[q[i]];
	for(RG int i=1; i<=n; i++){
		printf("%s ", Word[i]+1);
		printf("%d\n", ans[val[i]]);
	}
}
int MAIN(){
#define HAHA LALA
#ifdef HAHA
	freopen("ACautomata.in", "r", stdin);
	freopen("ACautomata.out", "w", stdout);
#endif
	read(n);
	for(int i=1; i<=n; i++){
		Gets(Word[i]); build(Word[i]);
	}
	getfail();
	Gets(P);
	find(P);
	return 0;
}
int AC = MAIN();
int main(){;}