HDOJ 1686 Oulipo：AC 自動機高效統計模式串出現次數

問題描述：給定模式串 W（長度 ≤ 10,000）和文本串 T（長度 ≤ 1,000,000），統計 W 在 T 中出現的次數（允許重疊）。字符集為大寫字母 A-Z。多測試用例。

為何選 AC 自動機？

雖然單模式匹配用 KMP 即可（O(|W|+|T|)），但 AC 自動機（Aho-Corasick）是多模式匹配的通用利器，且能輕鬆擴展到多模式場景。本題用 AC 自動機構建單模式的失敗指針樹，同樣高效。

核心步驟

1. 建 Trie：插入模式串 W，終結節點 end[node]++；
2. 構建失敗指針：BFS 遍歷 Trie，為每個節點計算 fail 指針，並補全轉移（缺失邊指向 fail 節點對應邊）；
3. 查詢匹配：沿文本串在自動機上行走，每到一節點沿 fail 鏈累加 end 值。為避免重複遍歷 fail 鏈，用 dp[node] 記憶該節點及其後綴匹配的總次數（動態規劃優化）。

關鍵代碼

const int MAXN = 11000;
int ch[MAXN][26], fail[MAXN], end[MAXN], dp[MAXN];
int Size, root;

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

int NewNode() {
    memset(ch[Size], -1, sizeof(ch[Size]));
    end[Size] = 0;
    return Size++;
}

void AC_Init() { Size = 0; root = NewNode(); }

void AC_Insert(char* s) {
    int u = root;
    for (int i = 0; s[i]; i++) {
        int c = idx(s[i]);
        if (ch[u][c] == -1) ch[u][c] = NewNode();
        u = ch[u][c];
    }
    end[u]++;
}

void AC_Build() {
    queue<int> q;
    fail[root] = root;
    for (int c = 0; c < 26; c++) {
        if (ch[root][c] == -1) ch[root][c] = root;
        else { fail[ch[root][c]] = root; q.push(ch[root][c]); }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int c = 0; c < 26; c++) {
            if (ch[u][c] == -1) ch[u][c] = ch[fail[u]][c];
            else { fail[ch[u][c]] = ch[fail[u]][c]; q.push(ch[u][c]); }
        }
    }
}

int AC_Query(char* s) {
    int u = root, ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; s[i]; i++) {
        u = ch[u][idx(s[i])];
        int v = u, sum = 0;
        while (v != root) {
            if (dp[v] != -1) { sum += dp[v]; break; }
            sum += end[v];
            v = fail[v];
        }
        dp[u] = sum;
        ans += sum;
    }
    return ans;
}

複雜度

• 構建：O(|W| · |Σ|)；
• 查詢：O(|T|) —— 每個字符只在自動機上走一步，dp 記憶化保證 fail 鏈每個節點最多被完整遍歷一次；
• 空間：O(|W| · |Σ|)。

AC 自動機將多模式匹配降維為單次線性掃描，是海量文本模式匹配的標準解法。