「一本通 2.4 练习 5」病毒

形式化题目

给定 $n$ 个非空 01 串构成的集合 $S$ （病毒代码段，总长度 $\leqslant 3\times 10^4$ ）。判断是否存在一个无限长的 01 串 $T$ ，使得 $T$ 的任意连续子串都不属于 $S$ ；存在输出 TAK，否则输出 NIE。

样例 $S=\{01,\ 11,\ 00000\}$ 的答案是 NIE：要避开 01，0 后面不能接 1；要避开 11，1 后面也不能接 1。于是每个字符后面都只能接 0，除第一位外整串全为 0——无论第一位取 0 还是 1，00000 都必然出现，任何无限长串都不安全。反过来，题面例子 $S=\{011,\ 11,\ 00000\}$ 中 $010101\cdots$ 不含 011、11、00000 中的任何一个，是安全的。

正解

思路

朴素想法：枚举安全前缀。 逐位构造答案，把每个"不含病毒串的前缀"看成一个状态：前缀 $p$ 读入位 $b$ 得到 $pb$ ，若 $pb$ 仍安全就连边 $p \to pb$ 。在这张"安全前缀图"上，有环就能沿环无限读下去，无环则安全路径只有有限条——问题的答案就是图中是否有环。但安全前缀有无穷多条（一旦存在环就无穷），无法显式枚举。

关键观察：状态可以合并。 读入下一位时，判断会不会踩雷只取决于当前串还有哪些后缀是某个病毒串的前缀，而其中最长的那个已经决定了其余的（其余都是它的真后缀）。把"最长匹配后缀落在哪个位置"建成 Trie，节点就成为安全前缀的有限等价类：从根到节点 $v$ 的串代表一类前缀，读入 $b$ 后的最长匹配后缀就是从 $v$ 沿 $b$ 走一步的结果（Trie 中没有这条边就沿 fail 指针回退）。这正是 AC 自动机，节点数不超过总长度 $+1$ 。

危险标记。 节点 $v$ 危险 $\iff$ 从根到 $v$ 的串含有病毒串作子串 $\iff$ $v$ 本身是病毒串结尾，或 $fail[v]$ 危险（fail 指向"最长且同时是某病毒串前缀"的真后缀，fail 链恰好枚举了所有这类后缀）。BFS 建 fail 时顺手做一次 END[w] |= END[fail[w]]，沿 fail 深度递增方向传播一遍即得全部危险标记。建 fail 的同时把 Trie 缺失边补成 TO[v][b] = TO[fail[v]][b]，此后每个节点读 0/1 都唯一落到另一个节点，得到一张每个点出度恰为 2 的完整转移图。

只看可达的安全子图。 从根出发只沿两端都安全的边 BFS，用 seen/total 得到真正能用到的安全子图并统计入度 indeg；随后用 Kahn 拓扑排序判环：入度归零的点入队、删除并回删出边，removed 计数——所有可达安全节点都能删光（removed == total）则无环，输出 NIE；有点永远删不掉（环上节点入度恒大于 0）则有环，输出 TAK。Kahn 是迭代实现，不受 Python 递归深度限制。

正确性上，两个方向都直接：有环时先沿安全路径走到环上，再无限绕环，每步都停在安全节点，拼出的无限串不含任何病毒串；无环时安全子图是 DAG，任何路径长度有限，逐位生成必然在有限步内踏入危险节点，即任何无限长串都会包含病毒串。

下图是样例 $\{01,\ 11,\ 00000\}$ 的可达安全子图，节点标签是该状态代表的前缀，边标签是读入的位（危险节点 01、11、00000 及指向它们的边已删除）：

graph LR
    r["ε（根）"] -->|0| a["0"]
    r -->|1| b["1"]
    b -->|0| a
    a -->|0| c["00"]
    c -->|0| d["000"]
    d -->|0| e["0000"]

所有路径最终都走进死路 $e$ ——它读 0 会进入 00000，读 1 会进入 01，两条边都被删除，所以图中无环，答案为 NIE。对照题面例子 $\{011,\ 11,\ 00000\}$ ：此时 0 与 01 都安全且互为转移（0 读 1 到 01，01 读 0 回到 0），环上的读位序列正是 $010101\cdots$ ，答案为 TAK。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 13:59
# update_at: 2026-09-30 14:07

import sys
from collections import deque


def build_pattern(strings: list[bytes]) -> tuple[list[list[int]], list[bool]]:
    """把所有病毒串插进 Trie，返回完整转移表 TO 与危险标记表 END。

    危险 = 该节点代表的串含有病毒串作子串 = 自身是病毒串结尾，或 fail 链上
    存在病毒串结尾；建 fail 时沿队列顺序传播一次即得。
    """
    TO = [[-1, -1]]  # 每个节点两条出边：0 位、1 位，-1 表示 Trie 中尚无此边
    END = [False]    # 节点对应串是否危险
    for s in strings:
        v = 0
        for byte in s:
            bit = byte & 1                     # '0'=48→0，'1'=49→1
            if TO[v][bit] == -1:
                TO[v][bit] = len(TO)
                TO.append([-1, -1])
                END.append(False)
            v = TO[v][bit]
        END[v] = True

    # BFS 建 fail：缺失边抄 fail 的同位边（补成完整转移表），已存在的边更新
    # fail 并把危险标记沿 fail 链传播给孩子。
    fail = [0] * len(TO)
    q = deque(w for w in TO[0] if w != -1)      # 根的孩子先入队
    TO[0] = [w if w != -1 else 0 for w in TO[0]]  # 根的缺失边指回自己
    while q:
        v = q.popleft()
        for bit in (0, 1):
            w = TO[v][bit]
            if w == -1:
                TO[v][bit] = TO[fail[v]][bit]   # 缺失边：抄 fail[v] 的同位边
            else:
                fail[w] = TO[fail[v]][bit]
                END[w] |= END[fail[w]]         # 危险沿 fail 链传播
                q.append(w)
    return TO, END


def has_cycle(TO: list[list[int]], END: list[bool]) -> bool:
    """从根只走安全边的可达子图中是否存在环：Kahn 删不光所有点即有环。"""
    safe = [not end for end in END]
    if not safe[0]:
        return False  # 病毒串非空时根恒安全，这里只防御空串输入

    # 可达安全子图：只沿两端都安全的边 BFS，同时统计入度
    seen = [False] * len(TO)
    indeg = [0] * len(TO)
    seen[0] = True
    q = deque([0])
    total = 1                             # 子图中的安全节点数
    while q:
        v = q.popleft()
        for bit in (0, 1):
            w = TO[v][bit]
            if safe[w]:
                indeg[w] += 1
                if not seen[w]:
                    seen[w] = True
                    total += 1
                    q.append(w)

    # Kahn：入度归零的点入队并回删出边；环上节点入度永不归零
    q = deque(i for i in range(len(TO)) if seen[i] and indeg[i] == 0)
    removed = 0
    while q:
        v = q.popleft()
        removed += 1
        for bit in (0, 1):
            w = TO[v][bit]
            if safe[w]:
                indeg[w] -= 1
                if indeg[w] == 0:
                    q.append(w)
    return removed != total


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    strings = [next(data) for _ in range(n)]
    TO, END = build_pattern(strings)
    print("TAK" if has_cycle(TO, END) else "NIE")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:52
 * update_at: 2026-10-05 03:52
 */
// AC 自动机 + 拓扑判环：是否存在无限长的安全 01 串。

#include <cstdio>
#include <string>
#include <queue>
using namespace std;

typedef long long ll;

const int MAXN = 30005 + 5; // 病毒串总长不超过 3e4，Trie 节点数不超过总长 + 1

int n;
int ch[MAXN][2];  // 补全后的转移表：ch[v][b] = 节点 v 读入位 b 后到达的节点
int fail_[MAXN];  // fail 指针：指向"最长且同时是某病毒串前缀"的真后缀
bool danger[MAXN];// danger[v] = 从根到 v 的串是否含有病毒串作子串
bool seen[MAXN];  // 从根沿安全边 BFS 时是否访问过
int indeg[MAXN];  // 可达安全子图中每个节点的入度
int tot = 1;      // Trie 节点数，0 是根，1 号起为真实节点（先占一个空位）

// 把一个病毒串插进 Trie
void insert_str(const string &s) {
    int v = 0;
    for (size_t i = 0; i < s.size(); i++) {
        int b = s[i] - '0';
        if (ch[v][b] == 0) { // 0 号保留为根，0 表示尚无此边
            ch[v][b] = ++tot;
        }
        v = ch[v][b];
    }
    danger[v] = true; // 病毒串结尾标记为危险
}

// BFS 建 fail 指针，同时补全转移表、沿 fail 链传播危险标记
void build_fail() {
    queue<int> q;
    for (int b = 0; b < 2; b++) {
        if (ch[0][b] != 0) {
            // 根的孩子 fail 指向根，缺省值 0 已正确，直接入队
            q.push(ch[0][b]);
        }
        // 根的缺失边 ch[0][b] == 0 恰好指回自己，无需处理
    }
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int b = 0; b < 2; b++) {
            int w = ch[v][b];
            if (w == 0) {
                // 缺失边：抄 fail[v] 的同位边，补成完整转移图
                ch[v][b] = ch[fail_[v]][b];
            } else {
                fail_[w] = ch[fail_[v]][b];
                // 危险沿 fail 链传播：w 的后缀里有病毒串结尾则 w 也危险
                danger[w] = danger[w] || danger[fail_[w]];
                q.push(w);
            }
        }
    }
}

// 判断是否存在无限长安全串：可达安全子图有环输出 true
bool solve() {
    // 从根出发，只沿两端都安全的边 BFS，统计可达安全节点和入度
    queue<int> q;
    seen[0] = true;
    q.push(0);
    int total = 1; // 可达安全节点数
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int b = 0; b < 2; b++) {
            int w = ch[v][b];
            if (danger[w]) continue; // 走过去会踩雷，删掉这条边
            indeg[w]++;
            if (!seen[w]) {
                seen[w] = true;
                total++;
                q.push(w);
            }
        }
    }

    // Kahn 拓扑排序：入度归零的点出队并回删出边；环上节点入度永不归零
    int removed = 0;
    for (int v = 0; v <= tot; v++) {
        if (seen[v] && indeg[v] == 0) q.push(v);
    }
    while (!q.empty()) {
        int v = q.front(); q.pop();
        removed++;
        for (int b = 0; b < 2; b++) {
            int w = ch[v][b];
            if (danger[w]) continue;
            indeg[w]--;
            if (indeg[w] == 0) q.push(w);
        }
    }
    return removed != total; // 删不光所有可达安全节点则必有环
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        static char buf[MAXN];
        scanf("%s", buf);
        insert_str(string(buf));
    }
    build_fail();
    printf(solve() ? "TAK\n" : "NIE\n");
    return 0;
}

复杂度

设病毒串总长度为 $L$ ，节点数 $N \leqslant L+1$ 。插串 $O(L)$ ；建 fail、补边、危险传播中每个节点的每条边只处理一次， $O(N)$ ；可达安全子图 BFS 与 Kahn 各 $O(N)$ （每点至多 2 条出边）。总计时间 $O(L)$ ，空间 $O(N)$ 。 $L \leqslant 3\times 10^4$ ，对 1000ms / 128MB 的限制非常宽裕。

总结

“是否存在无限长安全串"等价于"安全转移图中是否存在环”：有环则绕环无限读，无环则安全路径必然耗尽。
无穷多的安全前缀用 AC 自动机压缩成有限状态：最长匹配后缀决定一切，Trie 节点就是等价类。
危险标记沿 fail 链传播一次即完备；补全缺失边后，判环用迭代 Kahn 完成，输出 TAK / NIE。

「一本通 2.4 练习 5」病毒

目录

形式化题目

正解

思路

代码

复杂度

总结