题目描述

给我们若干个01病毒串,问我们是否存在长度无限的不包含病毒串的01串.
所有病毒代码段的总长度不超过 30000 .

样例

输入

3
01 
11 
00000

输出

NIE

分析

问我们是否存在不包含这些病毒串的01串,即有没有不经过非法节点的环,非法节点是终止节点和fail链上有终止节点的点.
如何判断有没有合法的环,我们可以枚举0和1,不走非法节点,用dfs的方式看看能不能构成环.
最坏情况把所有点遍历一遍O(N)

AC自动机

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4+10;
int tr[N][2],st[N],idx;
int q[N],fail[N];
int n;
char s[N];
int vs[N];
void insert()
{
    int u=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'0';
        if(!tr[u][t])tr[u][t]=++idx;
        u=tr[u][t];
    }
    st[u]=1;
}
void build()
{
    int hh=0,tt=0;
    for(int i=0;i<2;i++)
        if(tr[0][i])q[tt++]=tr[0][i];
    while(hh!=tt)
    {
        int t=q[hh++];
        for(int i=0;i<2;i++)
        {
            int u=tr[t][i];
            if(!u)tr[t][i]=tr[fail[t]][i];
            else
            {
                fail[u]=tr[fail[t]][i];
                q[tt++]=u;
                st[u]|=st[fail[u]];
            }
        }
    }
}
bool dfs(int u)
{
    if(vs[u]==1)return true;
    else if(vs[u]==-1)return false;

    vs[u]=1;
    for(int i=0;i<2;i++)
    {
        if(!st[tr[u][i]]&&dfs(tr[u][i]))return true;
    }
    vs[u]=-1;
    return false;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert();
    }
    build();
    if(dfs(0))puts("TAK");
    else puts("NIE");
    return 0;
}