病毒「POI 2000」

【题目描述】

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

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

请写一个程序，读入病毒代码，判断是否存在一个无限长的安全代码，将结果输出。

【输入格式】

第一行包括一个整数 \(n\)，表示病毒代码段的数目；
以下的 \(n\) 行，每一行都包括一个非空的 \(01\) 字符串——就是一个病毒代码段。

【输出格式】
假如存在这样的代码，则输出 TAK，否则输出 NIE。

题解

由于是AC自动机专题 所以我们不妨考虑一下怎么用AC自动机解决

显而易见 这个无限长的\(01\)串应该是有循环节的

把\(n\)个危险串插入AC自动机 在结束节点打标记

那么当你在AC自动机上对这个\(01\)循环串做匹配的时候，当前指针走的应该也是循环，并且 沿途经过的节点 以及 每个经过节点到根的fail链上 都没有结束节点

因为用AC自动机做匹配的时候不是走到每个节点都要跳fail 如果跳到有结束tag的就(文章包含单词数)+1吗 而这里我们希望它为0

所以我们把所有 有结束tag的节点 及 这个节点到根的fail链上有结束节点 的节点删掉(设为不可用)

然后在剩下的节点构成的这个不完整的AC自动机里找环 如果找得到就是有解 否则无解 找环像找强连通分量那么找就行 或者就dfs一下也行

注意特判一下自环

【代码】

#include <bits/stdc++.h>
using namespace std;

int n, len;
char s[100005];

int ch[100005][2], fail[100005], tot;
bool tag[100005];

inline void insert(char *str, int l) {
    int x = 0;
    for (int i = 1; i <= l; i++) {
        if (!ch[x][str[i] - '0']) {
            ch[x][str[i] - '0'] = ++tot;
        }
        x = ch[x][str[i] - '0'];
    }
    tag[x] = 1;
}

queue<int> q;

inline void getfail() {
    for (int i = 0; i < 2; i++) if (ch[0][i]) q.push(ch[0][i]);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        tag[x] |= tag[fail[x]];
        for (int i = 0; i < 2; i++) {
            if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
            else ch[x][i] = ch[fail[x]][i];
        }
    }
}

int dfn[30005], low[30005], stk[30005], tme, top;
bool vis[30005], flag;

void tarjan(int x) {
    dfn[x] = low[x] = ++tme; 
    vis[x] = 1; 
    stk[++top] = x; 
    for (int i = 0; i < 2; i++) {
        if (tag[ch[x][i]]) continue;
        int y = ch[x][i];
        if (x == y) flag = 1;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (vis[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (dfn[x] == low[x]) {
        int now = 0, totot = 0;
        do {
            now = stk[top--];
            vis[now] = 0;
            totot++;
        } while (now != x);
        if (totot > 1) flag = 1;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        memset(s, 0, sizeof(s));
        scanf("%s", s+1); len = strlen(s+1);
        insert(s, len);
    }
    getfail();
    flag = 0;
    tarjan(0);
    if (flag) puts("TAK");
    else puts("NIE");
    return 0;
}

病毒「POI 2000」

原文：https://www.cnblogs.com/ak-dream/p/AK_DREAM38.html