「POI2000」病毒-AC自动机

发表于 | 更新于 | 分类于 | | 阅读次数：
本文字数： 2.7k | 阅读时长 ≈ 5 分钟

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

链接

Luogu P2444

题解

对所有的模版串建立AC自动机，补全Trie图，在Trie图上找环。

注意这里不能到达单词结束的节点，也不能到达所有fail节点是单词结束的点。

代码

点击切换显示状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN = 1001000;

template <int sigma_size>
struct AC_automaton{
    bool vis[MAXN],flag;
    bool instack[MAXN];
    int f[MAXN],c[MAXN][sigma_size],end[MAXN];
    int root,cnt;
    AC_automaton(){root=cnt=0;}
    void clear(){}
    //qwq
    void insert(char *str){
        int n = strlen(str),nown = root;
        for(int i = 0;i<n;i++){
            if(!c[nown][str[i]-'0'])
                c[nown][str[i]-'0'] = ++cnt;
            nown = c[nown][str[i]-'0'];
        }
        end[nown] |= 1;
    }
    void get_fail(){
        queue<int> q;
        while(!q.empty()) q.pop();
        for(int i = 0;i<sigma_size;i++){
            if(c[root][i]){
                f[c[root][i]] = root;
                q.push(c[root][i]);
            }
        }
        while(!q.empty()){
            int nown = q.front();q.pop();
            for(int i = 0;i<sigma_size;i++){
                if(c[nown][i]){
                    f[c[nown][i]] = c[f[nown]][i];
                    end[c[nown][i]] |= end[f[c[nown][i]]];
                    q.push(c[nown][i]);
                }
                else c[nown][i] = c[f[nown]][i];
            }
        }
    }
    bool judge(){
        memset(vis,0,sizeof(vis));
        memset(instack,0,sizeof(instack));
        flag = 0;
        for(int i = 0;i<=cnt;i++){
            if(!vis[i] && !end[i]) flag |= dfs(i);
            if(flag) return true;
        }
        return false;
    }
    bool dfs(int x){
        instack[x] = vis[x] = 1;
        for(int i = 0;i<sigma_size;i++){
            int v = c[x][i];
            if(end[v]) continue;
            if(instack[v] || (!vis[v] && dfs(v))) 
                return true;
        }
        instack[x] = 0;
        return false;
    }
};

AC_automaton<2> AC;

int n;
char s[MAXN];

void init(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        scanf("%s",s);
        AC.insert(s);
    }
}

void solve(){
    AC.get_fail();
    if(AC.judge()){
        printf("TAK\n");
    }
    else{
        printf("NIE\n");
    }
}

int main(){
    init();
    solve();
    return 0;
}