|
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2938
这题写题解的人好像不多的样子……
首先我们把所有串建一个AC自动机 方便起见我们直接把fail指针合并到子结点
如果一个串能无限长,也就是说它可以在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;
}
| 
转播
