[Luogu2444][POI2000]病毒

Luogu

sol

如果存在一个合法的无限长的串，那势必说明在(AC)自动机上存在一个合法的环。由此转化为判环，只要判断搜到的点是否已经在搜索栈中即可。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100005;
int n,tot,l,ch[2][N],fail[N],frb[N],vis[N],ins[N];
char s[N];
queue<int>Q;
void Insert()
{
    scanf("%s",s);l=strlen(s);
    int x=0;
    for (int i=0;i<l;i++)
    {
        if (!ch[s[i]-'0'][x]) ch[s[i]-'0'][x]=++tot;
        x=ch[s[i]-'0'][x];
    }
    frb[x]=1;
}
void Get_Fail()
{
    for (int i=0;i<2;i++) if (ch[i][0]) Q.push(ch[i][0]);
    while (!Q.empty())
    {
        int u=Q.front();Q.pop();
        for (int i=0;i<2;i++)
            if (ch[i][u]) fail[ch[i][u]]=ch[i][fail[u]],Q.push(ch[i][u]);
            else ch[i][u]=ch[i][fail[u]];
        frb[u]|=frb[fail[u]];
    }
}
void dfs(int u)
{
    if (ins[u]) {puts("TAK");exit(0);}
    if (vis[u]) return;
    vis[u]=ins[u]=1;
    for (int i=0;i<2;i++)
        if (!frb[ch[i][u]]) dfs(ch[i][u]);
    ins[u]=0;
}
int main()
{
    scanf("%d
",&n);
    for (int i=1;i<=n;i++) Insert();
    Get_Fail();
    dfs(0);
    puts("NIE");
    return 0;
}