洛谷P2444 [POI2000]病毒 题解

题目链接：P2444 [POI2000]病毒

题意：

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果 $\{011, 11, 00000\}$ 为病毒代码段，那么一个可能的无限长安全代码就是 $010101 \ldots$。如果 $\{01, 11, 000000\}$ 为病毒代码段，那么就不存在一个无限长的安全代码。

现在给出所有的病毒代码段，判断是否存在无限长的安全代码。

$1 \leq n \leq 2000$，所有病毒代码段的总长度不超过 $3 \times 10^4$。

不难发现这是一个 $\tt{AC}$ 自动机的题目

考虑一个安全代码在 $\tt{AC}$ 自动机上是怎么跑的

显然它会从 $0$ 结点开始跑，然后最后在一个环上面跑

这个环显然不能包含「是字符串结尾的结点」

仔细想一想，其实不止这些结点！

对于一个结点 $u$ ，如果它的 $\tt{fail}$ 指针所指向的结点是「是字符串结尾的结点」

那么 $u$ 也是不能走的我们称这些结点为 「含病毒后缀的结点」

当然，如果一个结点的 $\tt{fail}$ 指针所指向的结点是「含病毒后缀的结点」，

那么这个结点也是「含病毒后缀的结点」，同样不可以走

说了这么多，其实只需要在板子上加一句

if(ed[fail[trie[u][i]]])++ed[trie[u][i]];

就好了

时间复杂度 $O(\sum |s_i|)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)
#define L (int)(3e4+15)
struct Trie
{
    queue<int> q;
    int tot,trie[L][2],ed[L],fail[L];
    void insert(string s)
    {
        int u=0;
        for(int i=0; i<s.size(); i++)
        {
            int c=s[i]-'0';
            if(!trie[u][c])trie[u][c]=++tot;
            u=trie[u][c];
        }
        ++ed[u];
    }
    void build()
    {
        for(int i=0; i<2; i++)
            if(trie[0][i])q.push(trie[0][i]);
        while(!q.empty())
        {
            int u=q.front(); q.pop();
            for(int i=0; i<2; i++)
            {
                if(trie[u][i])
                {
                    fail[trie[u][i]]=trie[fail[u]][i];
                    if(ed[fail[trie[u][i]]])++ed[trie[u][i]];
                    q.push(trie[u][i]);
                }else trie[u][i]=trie[fail[u]][i];
            }
        }
    }
    int ins[L],vis[L];
    bool dfs(int u)
    {
        ins[u]=1;
        for(int i=0; i<2; i++)
        {
            int v=trie[u][i];
            if(ins[v])return 1;
            if(vis[v]||ed[v])continue;
            vis[v]=1; if(dfs(v))return 1;
        }
        ins[u]=0;
        return 0;
    }
    void solve()
    {
        for(int i=1; i<=tot; i++)
            ins[i]=vis[i]=0;
        vis[0]=1;
        cout << (dfs(0)?"TAK\n":"NIE\n");
    }
}tr;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; string s;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> s;
        tr.insert(s);
    }
    tr.build();tr.solve();
    return 0;
}