记录编号	214461	评测结果	AAAAAAT
题目名称	AC自动机	最终得分	85
用户昵称	/k	是否通过	未通过
代码语言	C++	运行时间	1.472 s
提交时间	2015-12-15 21:00:21	内存使用	0.39 MiB

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct u
{
	u *e[26],*x;
	int d;
}*rt;
queue<u*>q;
int pr[10010],n;
string m[10010],s;
inline void gtrie(int a)
{
	u* r=rt;
	int o=m[a].size();
	for(int i=0;i<o;i++)
	{
		int p=m[a][i]-'a';
		if(r->e[p]==NULL)
			r->e[p]=new u();
		r=r->e[p];
	}
	r->d=a;
}
int main()
{
	freopen("ACautomata.in","r",stdin);
	freopen("ACautomata.out","w",stdout);
	rt=new u();
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>m[i];
		gtrie(i);
	}
	cin>>s;
	q.push(rt);
	while(!q.empty())
	{
		u *k=q.front();
		q.pop();
		for(int i=0;i<=25;i++)
		if(k->e[i])
		{
			u *p=k->x;
			while(p&&!p->e[i])
				p=p->x;
			if(!p)
				k->e[i]->x=rt;
			else
				k->e[i]->x=p->e[i];
			q.push(k->e[i]);
		}
	}
	int o=s.size();
	u *k=rt;
	for(int i=0;i<o;i++)
	{
		int p=s[i]-'a';
		if(k->e[p])
			k=k->e[p];
		else
		{
			while(k&&!k->e[p])
				k=k->x;
			if(!k)
				k=rt;
			else
				k=k->e[p];
		}
		u *pp=k;
		while(pp)
		{
			if(pp->d)
				pr[pp->d]++;
			pp=pp->x;
		}
	}
	for(int i=1;i<=n;i++)
		cout<<m[i]<<" "<<pr[i]<<endl;
}