HDU 3695：AC 自動機匹配病毒字符串（含反轉）

問題描述

給定 N 個病毒字符串（僅大寫字母），再給一個長文本串（可能包含 [k]c 形式的重複字符展開）。要求統計文本中出現了多少種不同的病毒串（包含正向與反向匹配）。

解題思路：AC 自動機 + 雙向匹配

1. 將所有病毒串插入 AC 自動機，構建 Trie、失敗指針、輸出鏈。
2. 解析輸入文本：遇到 [k]c 展開為 k 個字符 c。
3. 正向匹配一次，標記命中的病毒編號。
4. 將文本反轉，再匹配一次（等價於匹配反向病毒串）。
5. 統計被標記的病毒種類數。

關鍵數據結構

• g[maxn][26]：Trie 轉移表。
• fail[]：失敗指針，BFS 構建。
• tag[]：節點對應的病毒編號（0 表示無）。
• last[]：輸出鏈，指向最近的有 tag 的祖先節點。
• vis[]：病毒是否被匹配到。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 250000;
const int SIGMA = 26;

struct AhoCorasick {
    int sz;
    int g[MAXN][SIGMA];
    int tag[MAXN], fail[MAXN], last[MAXN];
    int vis[300], jump[300]; // vis: 標記病毒是否匹配; jump: 病毒編號到 tag 的映射
    int N; // 病毒數量

    void init() {
        sz = 1;
        tag[0] = 0;
        memset(g[0], 0, sizeof(g[0]));
    }

    int idx(char ch) { return ch - 'A'; }

    void insert(const char* s, int id) {
        int u = 0;
        for (int i = 0; s[i]; ++i) {
            int v = idx(s[i]);
            if (!g[u][v]) {
                tag[sz] = 0;
                memset(g[sz], 0, sizeof(g[sz]));
                g[u][v] = sz++;
            }
            u = g[u][v];
        }
        if (!tag[u]) tag[u] = id;
        jump[id] = tag[u];
    }

    void buildFail() {
        queue<int> q;
        for (int c = 0; c < SIGMA; ++c) {
            int u = g[0][c];
            if (u) { fail[u] = last[u] = 0; q.push(u); }
        }
        while (!q.empty()) {
            int r = q.front(); q.pop();
            for (int c = 0; c < SIGMA; ++c) {
                int u = g[r][c];
                if (!u) { g[r][c] = g[fail[r]][c]; continue; }
                q.push(u);
                int v = fail[r];
                while (v && !g[v][c]) v = fail[v];
                fail[u] = g[v][c];
                last[u] = tag[fail[u]] ? fail[u] : last[fail[u]];
            }
        }
    }

    void markMatched(int u) {
        if (vis[tag[u]]) return;
        vis[tag[u]] = 1;
        if (last[u]) markMatched(last[u]);
    }

    void match(const char* s) {
        int u = 0;
        for (int i = 0; s[i]; ++i) {
            int v = idx(s[i]);
            while (u && !g[u][v]) u = fail[u];
            u = g[u][v];
            if (tag[u]) markMatched(u);
            else if (last[u]) markMatched(last[u]);
        }
    }

    int solve(char* text) {
        memset(vis, 0, sizeof(vis));
        buildFail();
        match(text);
        reverse(text, text + strlen(text));
        match(text);
        int ans = 0;
        for (int i = 1; i <= N; ++i) if (vis[jump[i]]) ++ans;
        return ans;
    }
} ac;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        ac.init();
        scanf("%d", &ac.N);
        char w[1005];
        for (int i = 1; i <= ac.N; ++i) {
            scanf("%s", w);
            ac.insert(w, i);
        }
        char ch;
        char s[5100005];
        int mv = 0;
        getchar(); // 吃掉換行
        while ((ch = getchar()) != '\n') {
            if (ch == '[') {
                int x; char c;
                scanf("%d%c", &x, &c);
                for (int i = 0; i < x; ++i) s[mv++] = c;
                getchar(); // 吃掉 ']'
            } else s[mv++] = ch;
        }
        s[mv] = '\0';
        printf("%d\n", ac.solve(s));
    }
    return 0;
}

複雜度分析

• 構建 AC 自動機：O(總模式串長度 × Σ)。
• 匹配：O(文本長度)。
• 空間：O(總模式串長度 × Σ)。

本題文本長度可達 5×10⁶，需注意輸入解析效率與內存限制。