BZOJ 2938 病毒完整解析

給定 N 個 01 字串（模式），問是否存在一個無限長的 01 字串，不包含任何一個模式作為子串。N ≤ 100，總長度 ≤ 30000。

核心建模：AC 自動機 + 有向圖判環

1. 將所有模式插入 Trie 樹
2. 建立 AC 自動機失效指標，構建完整狀態轉移圖（每個節點對 0/1 都有確定轉移）
3. 標記所有「危險狀態」：該節點或其失效鏈上任一節點為模式結尾
4. 在非危險狀態構成的子圖中判環：有環 ⇒ 存在無限合法字串（輸出 TAK），無環 ⇒ 所有路徑有限長（輸出 NIE）

判環方法：拓撲排序（Kahn 算法）

對非危險節點計算入度，拓撲排序。若能訪問所有非危險節點 → 無環；否則有環。比 DFS 判環更穩健，避免遞迴深度問題。

完整 AC 程式碼

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

const int MAXN = 30300;

struct Node {
    int next[2] = {0, 0};
    int fail = 0;
    bool danger = false; // 是否為危險狀態
    int in_deg = 0;      // 拓撲排序入度
} trie[MAXN];

int node_cnt = 1; // 0 為根節點

void insert(const string& s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - '0';
        if (!trie[u].next[c]) trie[u].next[c] = node_cnt++;
        u = trie[u].next[c];
    }
    trie[u].danger = true;
}

void build_ac() {
    queue q;
    // 根節點的直接子節點
    for (int c = 0; c < 2; c++) {
        int v = trie[0].next[c];
        if (v) {
            trie[v].fail = 0;
            q.push(v);
        } else {
            trie[0].next[c] = 0; // 缺失轉移指向根
        }
    }
    
    // BFS 建立失效指標與補全轉移
    while (!q.empty()) {
        int u = q.front(); q.pop();
        trie[u].danger |= trie[trie[u].fail].danger; // 繼承失效鏈危險性
        
        for (int c = 0; c < 2; c++) {
            int v = trie[u].next[c];
            if (v) {
                trie[v].fail = trie[trie[u].fail].next[c];
                q.push(v);
            } else {
                trie[u].next[c] = trie[trie[u].fail].next[c];
            }
        }
    }
}

bool has_cycle() {
    queue q;
    int total_safe = 0;
    
    // 計算非危險節點入度
    for (int i = 0; i < node_cnt; i++) {
        if (trie[i].danger) continue;
        total_safe++;
        for (int c = 0; c < 2; c++) {
            int v = trie[i].next[c];
            if (!trie[v].danger) trie[v].in_deg++;
        }
    }
    
    // 入度為 0 的非危險節點入隊
    for (int i = 0; i < node_cnt; i++)
        if (!trie[i].danger && trie[i].in_deg == 0)
            q.push(i);
    
    int visited = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        visited++;
        for (int c = 0; c < 2; c++) {
            int v = trie[u].next[c];
            if (trie[v].danger) continue;
            if (--trie[v].in_deg == 0) q.push(v);
        }
    }
    
    return visited != total_safe; // 有節點未被訪問 → 有環
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while (cin >> n) {
        node_cnt = 1;
        fill(trie, trie + MAXN, Node());
        
        string s;
        for (int i = 0; i < n; i++) {
            cin >> s;
            insert(s);
        }
        
        build_ac();
        cout << (has_cycle() ? "TAK" : "NIE") << '\n';
    }
    return 0;
}

關鍵點總結

• 危險狀態傳播：danger[u] |= danger[fail[u]] 確保模式結尾及其所有擴展狀態均標記危險
• 轉移圖完整性：AC 自動機構建後，每個節點對 0/1 均有確定轉移，形成確定性有限自動機（DFA）
• 拓撲排序優於 DFS：非遞迴、無棧溢位風險、自然處理大圖
• 複雜度：O(總長度 × 字元集大小) = O(30000 × 2)，極快