题目地址：洛谷：【P2444】[POI2000]病毒 – 洛谷、BZOJ：Problem 2938. — [Poi2000]病毒

题目描述

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
1.在文本文件WIR.IN中读入病毒代码；
2.判断是否存在一个无限长的安全代码；
3.将结果输出到文件WIR.OUT中。

输入输出格式

输入格式：
在文本文件WIR.IN的第一行包括一个整数n(n≤2000)，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。

输出格式：
在文本文件WIR.OUT的第一行输出一个单词：
TAK——假如存在这样的代码；
NIE——如果不存在。

输入输出样例

输入样例#1：

3
01 
11 
00000

输出样例#1：

NIE

题解

这个题要找的是一个无限的安全代码，我们考虑用AC自动机的理论来做。
如果把AC自动机的fail和边全部看成有向边，这个图就叫做trie图，图上的某一条路径可以代表我们匹配的过程。安全代码的匹配过程中肯定是不会有不安全的代码段结尾的节点的，又因为无限长的安全代码匹配过程肯定是无限的，如果在trie图上找到一个环，使得环上不出现不安全代码的结尾，那么说明存在这样一个无限循环的安全代码。
因此本题的思路就是在trie图上DFS找环。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <queue>

const int MAXN = 30005;

int ch[MAXN][2], fail[MAXN], cnt;
bool val[MAXN];
std::queue<int> que;

inline void insert(char *str) {
    int p = 0;
    for(int i = 0; str[i]; i++) {
        if(!ch[p][str[i] - '0']) ch[p][str[i] - '0'] = ++cnt;
        p = ch[p][str[i] - '0'];
    }
    val[p] = true;
}

inline void calfail() {
    for(int i = 0; i <= 1; i++) {
        if(ch[0][i]) {
            fail[ch[0][i]] = 0;
            que.push(ch[0][i]);
        }
    }
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = 0; i <= 1; i++) {
            if(ch[u][i]) {
                fail[ch[u][i]] = ch[fail[u]][i];
                val[ch[u][i]] |= val[fail[ch[u][i]]];
                que.push(ch[u][i]);
            } else {
                ch[u][i] = ch[fail[u]][i];
            }
        }
    }
}

bool vis[MAXN], visd[MAXN], success = false;

inline void dfs(int p) {
    vis[p] = true;
    for(int i = 0; i <= 1; i++) {
        if(vis[ch[p][i]]) {
            success = true;
            return;
        }
        if(!val[ch[p][i]] && !visd[ch[p][i]]) {
            visd[ch[p][i]] = true;
            dfs(ch[p][i]);
            if(success) return;
        }
    }
    vis[p] = false;
}

int n;
char str[MAXN];

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%s", str);
        insert(str);
    }
    calfail();
    dfs(0);
    puts(success ? "TAK" : "NIE");
    return 0;
}