HDU 3695 Computer Virus on Planet Pandora：AC 自動機多模式匹配

問題描述

給定 n 個病毒特徵串，最後一個字串經過特殊展開（含反向），問其中出現了多少種不同的病毒特徵串。

AC 自動機構建

1. 插入所有模式串，終點節點 val++ 記錄編號/計數
2. BFS 建立 fail 指標：fail 指向最長真後綴對應的節點
3. 匹配時沿 fail 鏈輸出所有匹配模式

特殊字串展開

輸入字串含 [k]c 形式，表示字元 c 重複 k 次。需展開正向與反向兩個字串並分別匹配。

核心程式碼

struct Node {
    int val; Node *next[26], *fail;
    Node() : val(0), fail(nullptr) { memset(next, 0, sizeof(next)); }
};

void insert(char *s) { ... }
void build() { ... } // BFS 建 fail
void find(char *s) { // 匹配並計數
    Node *p = root;
    for (char c : s) {
        int id = c - 'A';
        while (p != root && !p->next[id]) p = p->fail;
        p = p->next[id] ? p->next[id] : root;
        for (Node *t = p; t != root; t = t->fail)
            if (t->val > 0) { ans += t->val; t->val = 0; } // 避免重複計數
            else break;
    }
}

完整流程

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        ans = 0; root = new Node();
        int n; scanf("%d", &n);
        while (n--) { char s[1111]; scanf("%s", s); insert(s); }
        build();
        scanf("%s", s1); expand(s1, s2, s3); // 展開正反兩串
        find(s2); find(s3);
        printf("%d\n", ans);
        deleteTrie(root);
    }
    return 0;
}

關鍵細節

• 節點池分配避免 new 開銷
• 匹配時 t->val = 0 確保每種病毒只計數一次
• 展開函數處理 [123]A 形式
• 記憶體釋放避免洩漏