BZOJ 2938 Poi2000 病毒 AC自动机+拓扑排序

题目大意:给定n个01串,问是否存在一个无限长的01串,不包含这n个01串中的任何一个

建出Trie图之后判环即可

我这傻逼一开始居然跑了一个DFS去判环23333

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 30300
using namespace std;
int n;
char s[M];
namespace Aho_Corasick_Automaton{
	struct Trie{
		Trie *son[2],*fail;
		bool ed;short into;
	}*root,mempool[M],*C=mempool;
	void Insert(Trie *&p,char *pos)
	{
		if(!p) p=new (C++)Trie;
		if(!*pos)
		{
			p->ed=true;
			return ;
		}
		Insert(p->son[*pos-'0'],pos+1);
	}
	void Build_Tree()
	{
		static Trie *q[M];
		int i,r=0,h=0;
		for(i=0;i<2;i++)
			if(root->son[i])
				(q[++r]=root->son[i])->fail=root;
			else
				root->son[i]=root;
		while(r!=h)
		{
			Trie *p=q[++h];
			for(i=0;i<2;i++)
			{
				if(p->son[i])
				{
					p->son[i]->fail=p->fail->son[i];
					p->son[i]->ed|=p->son[i]->fail->ed;
					q[++r]=p->son[i];
				}
				else
					p->son[i]=p->fail->son[i];
			}
		}
	}
	bool Find_Ring()
	{
		static Trie *temp,*q[M];
		int i,r=0,h=0,cnt=0;
		for(temp=mempool;temp<C;temp++)
			if(!temp->ed)
			{
				++cnt;
				for(i=0;i<2;i++)
					temp->son[i]->into++;
			}
		for(temp=mempool;temp<C;temp++)
			if(!temp->into&&!temp->ed)
				q[++r]=temp;
		while(r!=h)
		{
			Trie *p=q[++h];
			for(i=0;i<2;i++)
				if(!--p->son[i]->into&&!p->son[i]->ed)
					q[++r]=p->son[i];
		}
		return cnt!=r;
	}
}
int main()
{
	using namespace Aho_Corasick_Automaton;
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		Insert(root,s+1);
	}
	Build_Tree();
	puts(Find_Ring()?"TAK":"NIE");
	return 0;
}


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。