您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 2896 病毒侵襲：AC 自動機多模式匹配模板題詳解

編輯：關於C++

題目大意

給定 n 個病毒特徵串，再給 m 個網頁內容串。對每個網頁，輸出出現過的病毒特徵串編號（按輸入順序），並統計總共多少個網頁中毒。

AC 自動機核心結構

Trie 字典樹：存儲所有模式串，節點含 ch[字符集大小] 轉移指針
Fail 指針：當前節點匹配失敗時跳轉的最長真後綴節點（類似 KMP 的 next 數組）
Output 鏈表：last[u] 指向以 u 為後綴的最近模式串結尾節點，用於輸出所有匹配模式

關鍵算法流程

1. 插入模式串

void insert(char *s, int id) {
    int u = 0;
    for (int i = 0; s[i]; ++i) {
        int c = s[i]; // 直接用 ASCII 碼
        if (!ch[u][c]) {
            ch[u][c] = ++sz;
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz] = 0;
        }
        u = ch[u][c];
    }
    val[u] = id; // 模式串編號（1-based）
}

2. 構建 Fail 指針 (BFS)

void build_fail() {
    queue q;
    fail[0] = 0;
    // 初始化根的直接子節點
    for (int c = 0; c < SIGMA_SIZE; ++c) {
        int u = ch[0][c];
        if (u) { fail[u] = 0; q.push(u); last[u] = 0; }
    }
    // BFS 擴展
    while (!q.empty()) {
        int r = q.front(); q.pop();
        for (int c = 0; c < SIGMA_SIZE; ++c) {
            int u = ch[r][c];
            if (!u) continue;
            q.push(u);
            int v = fail[r];
            while (v && !ch[v][c]) v = fail[v];
            fail[u] = ch[v][c];
            // 輸出鏈表：若 fail 節點是模式串尾則指向它，否則繼承其 last
            last[u] = val[fail[u]] ? fail[u] : last[fail[u]];
        }
    }
}

3. 匹配文本

bool match(char *T) {
    int j = 0;
    for (int i = 0; T[i]; ++i) {
        int c = T[i];
        while (j && !ch[j][c]) j = fail[j];
        j = ch[j][c];
        if (val[j]) { print(j); return true; }
        if (last[j]) { print(last[j]); return true; }
    }
    return false;
}
void print(int j) {
    if (j) { cnt[val[j]]++; print(last[j]); } // 遞歸輸出鏈上所有模式
}

完整代碼架構

#include 
using namespace std;
const int MAXNODE = 500*210 + 10; // n≤500, len≤210
const int SIGMA_SIZE = 128; // ASCII
int ch[MAXNODE][SIGMA_SIZE];
int fail[MAXNODE], val[MAXNODE], last[MAXNODE];
int cnt[555], sz;

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    while (cin >> n) {
        // 初始化
        sz = 1; memset(ch[0], 0, sizeof(ch[0]));
        memset(val, 0, sizeof(val));
        memset(last, 0, sizeof(last));
        // 讀入病毒特徵串
        for (int i = 1; i <= n; ++i) {
            string s; cin >> s;
            insert(s.c_str(), i);
        }
        build_fail();
        // 處理網頁
        cin >> m;
        int total = 0;
        for (int i = 1; i <= m; ++i) {
            string s; cin >> s;
            memset(cnt, 0, sizeof(cnt));
            if (match(s.c_str())) {
                cout << "web " << i << ":";
                for (int j = 1; j <= n; ++j)
                    if (cnt[j]) cout << " " << j;
                cout << "\n";
                ++total;
            }
        }
        cout << "total: " << total << "\n";
    }
    return 0;
}