BZOJ2938
如果存在一个无限长的安全代码段，就是不停的匹配但无法匹配到标记节点。也就是AC自动机中Trie图成环（不包含被标记点）。建完Trie图后找环即可。
【代码】
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define N 30005
using namespace std;
typedef long long ll;
const int mod=
10007;
ll read()
{
ll x=
0,f=
1;
char ch=getchar();
while(!
isdigit(ch)){
if(ch==
'-')f=-
1;ch=getchar();}
while(
isdigit(ch)){x=(x<<
1)+(x<<
3)+ch-
'0';ch=getchar();}
return x*f;
}
char ch[N];
int n,m,cnt,ans;
int g[N][
2],Next[N];
bool tag[N];
void Add()
{
int len=
strlen(ch);
int now=
0;
for(
int i=
0;i<len;i++)
{
if(!g[now][ch[i]-
'0']) g[now][ch[i]-
'0']=++cnt;
now=g[now][ch[i]-
'0'];
}
tag[now]=
1;
}
void Input_Init()
{
n=read();
for(
int i=
1;i<=n;i++)
{
scanf(
"%s",ch);
Add();
}
}
void Construct_Automation()
{
queue<int>q;
q.push(
0);
while(!q.empty())
{
int k=q.front();q.pop();
for(
int i=
0;i<
2;i++)
{
int &v=g[k][i];
if(v)
{
q.push(v);
Next[v]=k==
0?
0:g[Next[k]][i];
}
else v=k==
0?
0:g[Next[k]][i];
tag[k]|=tag[Next[k]];
}
}
}
int Flag[N];
bool Dfs(
int x)
{
Flag[x]=-
1;
for(
int i=
0;i<=
1;i++)
{
int v=g[x][i];
if(tag[v]||Flag[v]==
1)
continue;
if(Flag[v]==-
1)
return true;
if(Dfs(v))
return true;
}
Flag[x]=
1;
return false;
}
void Solve(){
printf(Dfs(
0)?
"TAK":
"NIE");
}
int main()
{
Input_Init();
Construct_Automation();
Solve();
return 0;
}
