HDU 2896：病毒檢測 - AC 自動機多模式匹配

問題描述

給定 n 個病毒特徵串（關鍵詞），再給 m 個網頁內容串。對每個網頁，輸出出現過的病毒編號（按升序），最後輸出總共檢測到病毒的網頁數。字符集為可見 ASCII（32~126），總長度較大。

核心算法：Aho-Corasick 自動機

1. 構建 Trie：插入所有模式串，終結節點標記模式編號。
2. 構建失配指針 fail：BFS 層序構建，fail[u] 指向最長真後綴對應的 Trie 節點。
3. 匹配：遍歷文本串，沿 fail 鏈收集所有匹配的模式編號，用 vis 時間戳去重。

關鍵實現細節

• 字符映射：ch - 32 對應 0~94，或直接開 128 大小 next 數組。
• 節點池：靜態分配 struct Node { int next[128], fail, output; }，避免動態分配開銷。
• 去重：每個網頁一個全局 timer，節點 last_vis 記錄最後訪問的網頁編號，last_vis == timer 表示已計數。

代碼框架

struct Node {
    int next[128];
    int fail;
    int id; // 模式編號，0 表示無
    int last_vis;
    Node() { memset(next, 0, sizeof(next)); fail = 0; id = 0; last_vis = 0; }
} nodes[MAX_NODES];

int node_cnt = 1; // 0 為根

void insert(const char* s, int id) {
    int u = 0;
    for (; *s; ++s) {
        int c = *s - 32;
        if (!nodes[u].next[c]) nodes[u].next[c] = node_cnt++;
        u = nodes[u].next[c];
    }
    nodes[u].id = id;
}

void build_fail() {
    queue<int> q;
    for (int c = 0; c < 128; ++c) {
        int v = nodes[0].next[c];
        if (v) { nodes[v].fail = 0; q.push(v); }
        else nodes[0].next[c] = 0;
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int c = 0; c < 128; ++c) {
            int v = nodes[u].next[c];
            if (!v) {
                nodes[u].next[c] = nodes[nodes[u].fail].next[c];
            } else {
                nodes[v].fail = nodes[nodes[u].fail].next[c];
                q.push(v);
            }
        }
    }
}

void query(const char* s, int web_id, vector<int>& found) {
    int u = 0;
    for (; *s; ++s) {
        u = nodes[u].next[*s - 32];
        for (int v = u; v; v = nodes[v].fail) {
            if (nodes[v].last_vis == web_id) break;
            nodes[v].last_vis = web_id;
            if (nodes[v].id) found.push_back(nodes[v].id);
        }
    }
}

複雜度

• 構建：O(總模式長度 * 字符集)。
• 匹配：O(文本長度 + 匹配數)。
• 空間：O(總模式長度 * 字符集)。

總結

AC 自動機是多模式匹配的標準解法，本題考察完整流程：Trie 構建、Fail 指針 BFS、匹配時沿 Fail 鏈輸出並去重。注意字符集範圍與靜態內存池優化。