【BZOJ】【P 2938】【Poi 2000】【ウイルス】【問題解】【ACオートマトン】

転送ゲート:http://www.lydsy.com/JudgeOnline/problem.php?id=2938
この問題を書く人はあまりいないようですが・・・
まず、ACオートマチックをすべて直列に構築します.便宜上、failポインタをサブノードに直接統合します.
もし1つの列が無限に長いならば、つまりそれはACオートマチックの上でずっとマッチングすることができて、しかしマッチングしません
すなわちマッチングポインタはvalが1のノードに到達できず,この点をxとする.
つまりroot..xはウイルス列です
failポインタがxを指すyも歩けない
root..xはroot..yの接尾辞だから
処理して有向図にループがあるか否かを判断する
dfsでいい
Code:

#include<bits/stdc++.h>
using namespace std;
int n;
char s[30001];
struct node{
	int id,val;
	node *go[2],*fail,*last;
	node(node *C=0){
		id=0;fail=C;val=0;last=C;
		for(int i=0;i<2;i++)go[i]=C;
	}
}*Null,*root;
node *newnode(node *C){
	static int cnt=0;
	node *x=new node(C);
	x->id=++cnt;return x;
}
void insert(const char *s){
	node *u=root;int len=strlen(s);
	for(int i=0;i<len;i++){
		int v=s[i]-'0';
		if(u->go[v]==Null)u->go[v]=newnode(root);
		u=u->go[v];
	}u->val=1;
}
void get_fail(){
	queue<node*>q;
	for(int i=0;i<2;i++)if(root->go[i]!=Null)
	q.push(root->go[i]),root->go[i]->fail=root->go[i]->last=root;
	while(!q.empty()){
		node *u=q.front(),*v;q.pop();
		for(int i=0;i<2;i++)if((v=u->go[i])!=Null){
			q.push(v);node *j=u->fail;
			while(j!=Null&&j->go[i]==Null)j=j->fail;
			v->fail=j->go[i];v->val|=v->fail->val;
			v->last=v->fail->val?v->fail:v->fail->last;
		}else u->go[i]=u->fail->go[i];
	}
}
short vis[30001*2];
short ins[30001*2];
bool dfs(node *u){
	ins[u->id]=1;node *v;
	for(int i=0;i<2;i++){
		v=u->go[i];
		if(v->val)continue;
		if(ins[v->id])return 1;
		if(vis[v->id])continue;
		vis[v->id]=1;
		if(dfs(v))return 1;
	}ins[u->id]=0;
	return false;
}
int main(){
	Null=newnode(0);
	Null->fail=Null;Null->last=Null;
	for(int i=0;i<2;i++)Null->go[i]=Null;
	root=Null;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%s",s),insert(s);
	get_fail();vis[1]=1;
	puts(dfs(root)?"TAK":"NIE");
	return 0;
}