HDU 3065 病毒侵襲持續中：AC 自動機統計模式串出現次數

題目差異

HDU 2896 只需判斷「是否出現」，本題要求統計 n 個模式串在一個長文本（≤ 2×10⁶）中**各自出現的次數**。

核心修改點

1. match 函數返回 void，不再提前返回，需掃描完整文本
2. print 遞歸累加 cnt[val[j]]++，計數而非標記
3. 字符集優化：題目暗示大寫字母，SIGMA_SIZE=199（代碼中較大，可改 26）
4. 長文本用靜態 char s[2000000+10] 讀入

關鍵代碼變化

void match(char *T) {
    int n = strlen(T);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        int c = T[i] - 'A'; // 索引映射
        while (j && !ch[j][c]) j = fail[j];
        j = ch[j][c];
        // 輸出鏈表上所有模式串計數++
        for (int k = j; k; k = last[k])
            if (val[k]) cnt[val[k]]++;
    }
}
// 主函數讀入單個長文本，匹配後輸出所有 cnt>0 的模式串及其次數
int main() {
    while (cin >> n) {
        init();
        for (int i = 1; i <= n; ++i) {
            cin >> buf[i];
            insert(buf[i], i);
        }
        build_fail();
        cin >> s;
        match(s);
        for (int i = 1; i <= n; ++i)
            if (cnt[i]) cout << buf[i] << ": " << cnt[i] << "\n";
    }
}

優化：輸出鏈表遍歷去重

代碼中 for (int k=j; k; k=last[k]) 直接遍歷輸出鏈表，若模式串有包含關係（如 "ABC" 和 "BC"），同一位置會觸發多次計數，**這正是題目要求**（統計每個模式串獨立出現次數）。

複雜度

• 構建：O(總模式長 × Σ)
• 匹配：O(文本長 + 總匹配輸出次數)
• 最壞情況：文本 "AAAAA..." 模式 "A", "AA", "AAA"... 每位置輸出 O(n) 次，總 O(n×文本長)。但題目數據通常不會極端。

工程注意事項

1. 文本長 2×10⁶，**必須用靜態字符數組**，避免 string 重複分配
2. cnt 數組大小 ≥ n+1，每次測試用例 memset 清零
3. 輸入可能包含多測試用例，while(cin>>n) 循環處理