bzoj 2754: [SCOI2012]喵星球上的点名【AC自动机】

洛谷90，最后一个点死活卡不过去（也可能是我写的有问题？

比较暴力的做法，把询问带着标号建立AC自动机，用map存儿子。

然后用名字串在自动机上跑，以为是名或姓的子串就行所以把名和姓中间加个特殊字符拼起来即可。

注意trie的根最好设为1（now=1），然后把c[0][x]初始为1

#include<cstdio>

#include<map>

#include<queue>

#include<vector>

using namespace std;

const int N=100005;

int n,m,s[N],a1[N],a2[N],v[N],mk[N],ti;

vector<int>a[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

struct aczidongji

{

	int fa[N],tot;

	map<int,int>c[N];

	vector<int>po[N];

	void init()

	{

		tot=1;

		for(int i=-1;i<=10000;i++)

			c[0][i]=1;

		fa[1]=0;

	}

	void build(int p)

	{

		int now=1,n=read();

		for(int i=1;i<=n;i++)

		{

			int x=read();

			if(!c[now][x])

				c[now][x]=++tot;

			now=c[now][x];

		}

		po[now].push_back(p);

	}

	void par()

	{

		queue<int>q;

		q.push(1);

		while(!q.empty())

		{

			int u=q.front();

			q.pop();

			for(map<int,int>::iterator i=c[u].begin();i!=c[u].end();i++)

			{

				int t=i->first,k=fa[u];

				while(!c[k][t])

					k=fa[k];

				fa[i->second]=c[k][t];

				q.push(i->second);

			}

		}

	}

	void clc(int id,int x)

	{

		for(int i=x;i;i=fa[i])

			if(v[i]!=ti)

			{

				v[i]=ti;

				int len=po[i].size();

				for(int j=0;j<len;j++)

					if(mk[po[i][j]]!=ti)

					{

						mk[po[i][j]]=ti;

						a1[po[i][j]]++;

						a2[id]++;

					}

			}

			else

				break;

	}

	void wk(int x)

	{

		ti++;

		int now=1,len=a[x].size();

		for(int i=0;i<len;i++)

		{

			for(int t=a[x][i];!c[now][t];now=fa[now]);

			now=c[now][a[x][i]];

			clc(x,now);

		}

	}

}ac;

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;i++)

	{

		int z=read();

		while(z--)

		{

			int x=read();

			a[i].push_back(x);

		}

		a[i].push_back(-1);

		z=read();

		while(z--)

		{

			int x=read();

			a[i].push_back(x);

		}

	}

	ac.init();

	for(int i=1;i<=m;i++)

		ac.build(i);//cerr<<"build"<<endl;

	ac.par();//cerr<<"par"<<endl;

	for(int i=1;i<=n;i++)

		ac.wk(i);//cerr<<"wk"<<endl;

	for(int i=1;i<=m;i++)

		printf("%d\n",a1[i]);

	for(int i=1;i<=n;i++)

		printf("%d ",a2[i]);

	return 0;

}

巴特西

bzoj 2754: [SCOI2012]喵星球上的点名【AC自动机】

最新文章

热门文章