记录编号	261467	评测结果	AAAAAAAAAA
题目名称	[SCOI 2012] 喵星球上的点名	最终得分	100
用户昵称	小一米	是否通过	通过
代码语言	C++	运行时间	1.515 s
提交时间	2016-05-17 18:52:27	内存使用	48.55 MiB

#include"bits/stdc++.h"
#define M 1000006
#define LL long long
using namespace std;
int n,m,root=1,cnt=1;
int fail[M],len[2][M/5],vis[M],sum[M],ans[M],hash[M>>1];
map<int,int>trie[M];
vector<int> name[2][M/5],son[M],ID[M];
int in()
{
	int t=0;char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) t=(t<<1)+(t<<3)+ch-48,ch=getchar();
	return t;
}
void insert(int len,int id)
{
	int x,now=root;
	for (int i=0;i<len;i++)
	{
		x=in();
		if (!trie[now][x])
			trie[now][x]=++cnt,
			son[now].push_back(x);
		now=trie[now][x];
	}
	ID[now].push_back(id);
	hash[id]=now;
}
void build()
{
	queue<int>q;
	q.push(root);
	while(!q.empty())
	{
		int k=q.front();q.pop();
		for (int i=0;i<son[k].size();i++)
		{
			int tmp=fail[k],x=trie[k][son[k][i]];
			while (tmp&&!trie[tmp][son[k][i]]) tmp=fail[tmp];
			if (k!=root&&tmp) fail[x]=trie[tmp][son[k][i]];
			else fail[x]=root;
			q.push(x);
		}
	}
}
main()
{
	freopen("wtfname.in","r",stdin);
	freopen("wtfname.out","w",stdout);
	n=in();m=in();
	for (int i=1;i<=n;i++)
		for (int j=0;j<2;j++)
		{
			len[j][i]=in();
			for (int k=1;k<=len[j][i];k++)
				name[j][i].push_back(in());
		}
	for (int i=1;i<=m;i++)
		insert(in(),i);
	build();
	for (int i=1;i<=n;i++)
		for (int j=0;j<2;j++)
		{
			int now=root,tmp;
			for (int k=0;k<len[j][i];k++)
			{
				while (now&&!trie[now][name[j][i][k]]) now=fail[now];
				if (!now) now=root;
				else now=trie[now][name[j][i][k]];
				tmp=now;
				for (;tmp!=root;tmp=fail[tmp])
					if (ID[tmp].size()&&vis[tmp]!=i)
						vis[tmp]=i,
						ans[i]+=ID[tmp].size(),
						sum[tmp]++;
			}
		}
	for (int i=1;i<=m;i++) printf("%d\n",sum[hash[i]]);
	for (int i=1;i<=n;i++) printf("%d ",ans[i]);
}