NYOJ 1085 數單詞：AC 自動機模板題深度解析與優化實現

問題描述

給定 n 個查詢單詞（可能重複），及一篇長度 ≤ 10^6 的小寫英文文章。統計每個查詢單詞在文章中出現的次數（作為子串），輸出最大出現次數，並按輸入順序輸出所有達到最大值的單詞（重複單詞全部輸出）。T ≤ 200, n ≤ 150, 單詞長 ≤ 100。

為什麼選 AC 自動機？

• 多模式匹配： 同時匹配 n 個模式串，避免 O(n × |text|) 的暴力掃描。
• 線性複雜度： 建 Trie O(總模式長)，建失敗指針 O(節點數 × 字符集)，掃描文本 O(|text|)。
• 處理重複模式： 同一單詞多次查詢需全部輸出，需在 Trie 葉節點記錄所有對應的查詢編號。

核心資料結構設計

const int SIGMA = 26;           // 小寫字母
const int MAXNODE = 20000;      // 最大節點數：150 × 100 + 1
const int MAXP = 200;           // 最大模式數

struct ACAutomaton {
    int ch[MAXNODE][SIGMA];     // 轉移表
    int fail[MAXNODE];          // 失敗指針
    int val[MAXNODE];           // 該節點對應的模式編號（0 表示無）
    int last[MAXNODE];          // 輸出鏈：指向下一個有 val 的失敗祖先
    int cnt[MAXP];              // 每個模式的匹配計數
    int sz;                     // 當前節點總數

    // 輔助：單詞字串 -> 模式編號 映射（處理重複單詞）
    unordered_map<string, int> idMap;  // 或用 map<string, vector<int>> 記錄所有編號
};

關鍵演算法細節

1. 插入模式串 — 記錄所有查詢編號

void insert(const char* s, int idx) {  // idx: 1-based 查詢編號
    int u = 0;
    for (int i = 0; s[i]; ++i) {
        int c = s[i] - 'a';
        if (!ch[u][c]) {
            ch[u][c] = sz;
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz] = 0;
            ++sz;
        }
        u = ch[u][c];
    }
    val[u] = idx;                    // 葉節點記錄編號
    idMap[string(s)] = idx;          // 映射單詞到編號（最後一個編號）
}

注意： 若單詞重複出現，val[u] 只保留最後一個編號。輸出時需遍歷原始輸入陣列，通過 idMap 查找該單詞對應的計數。

2. 建立失敗指針（BFS）— 輸出鏈優化

void buildFail() {
    queue<int> q;
    fail[0] = 0;
    for (int c = 0; c < SIGMA; ++c) {
        int u = ch[0][c];
        if (u) {
            fail[u] = 0;
            last[u] = 0;
            q.push(u);
        }
    }
    while (!q.empty()) {
        int r = q.front(); q.pop();
        for (int c = 0; c < SIGMA; ++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[u] 有 val 直接指向它，否則繼承其 last
            last[u] = val[fail[u]] ? fail[u] : last[fail[u]];
        }
    }
}

3. 文本掃描與計數 — 遞歸輸出鏈

void printMatch(int j) {  // 遞歸輸出鏈上所有匹配
    if (j) {
        cnt[val[j]]++;
        printMatch(last[j]);
    }
}

void query(const 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];
        if (val[j]) printMatch(j);
        else if (last[j]) printMatch(last[j]);
    }
}

完整 Accepted 程式碼（優化版）

#include <bits/stdc++.h>
using namespace std;

const int SIGMA = 26;
const int MAXNODE = 20000;
const int MAXP = 200;
const int MAXLEN = 1000005;

struct ACAutomaton {
    int ch[MAXNODE][SIGMA];
    int fail[MAXNODE], val[MAXNODE], last[MAXNODE];
    int cnt[MAXP];
    int sz;
    unordered_map<string, int> mp;  // 單詞 -> 最後編號

    void init() {
        sz = 1;
        memset(ch[0], 0, sizeof(ch[0]));
        memset(cnt, 0, sizeof(cnt));
        mp.clear();
    }

    void insert(const char* s, int v) {
        int u = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - 'a';
            if (!ch[u][c]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        val[u] = v;
        mp[string(s)] = v;
    }

    void buildFail() {
        queue<int> q;
        fail[0] = 0;
        for (int c = 0; c < SIGMA; ++c) {
            int u = ch[0][c];
            if (u) {
                fail[u] = 0;
                last[u] = 0;
                q.push(u);
            }
        }
        while (!q.empty()) {
            int r = q.front(); q.pop();
            for (int c = 0; c < SIGMA; ++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];
                last[u] = val[fail[u]] ? fail[u] : last[fail[u]];
            }
        }
    }

    void printMatch(int j) {
        if (j) {
            cnt[val[j]]++;
            printMatch(last[j]);
        }
    }

    void query(const 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];
            if (val[j]) printMatch(j);
            else if (last[j]) printMatch(last[j]);
        }
    }
} ac;

char text[MAXLEN];
char patterns[MAXP][105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        ac.init();
        for (int i = 1; i <= n; ++i) {
            scanf("%s", patterns[i]);
            ac.insert(patterns[i], i);
        }
        ac.buildFail();
        scanf("%s", text);
        ac.query(text);
        int maxCnt = 0;
        for (int i = 1; i <= n; ++i) maxCnt = max(maxCnt, ac.cnt[i]);
        printf("%d\n", maxCnt);
        for (int i = 1; i <= n; ++i) {
            int id = ac.mp[string(patterns[i])];
            if (ac.cnt[id] == maxCnt) printf("%s\n", patterns[i]);
        }
    }
    return 0;
}

易錯點與優化提示

1. 重複單詞處理： 輸出時必須按原始輸入順序遍歷 patterns[i]，通過 mp 查找其對應的計數索引，而非直接用 i。
2. 字符集固定為 26 小寫： 直接用陣列 ch[MAXNODE][26] 比 map/unordered_map 快 10 倍以上。
3. 遞歸輸出鏈深度： 極端情況下鏈長可達模式串長度，遞歸可能棧溢出，建議改為迴圈：

void printMatch(int j) {
    for (int u = j; u; u = last[u]) cnt[val[u]]++;
}

4. 靜態陣列大小： MAXNODE = 總模式長度 + 1，本題 150 × 100 + 5 = 15005，開 20000 稳妥。
5. 多測試用例初始化： 每個 case 必須 init() 重置 sz, cnt, mp, ch[0]。

複雜度分析

AC 自動機是多模式匹配的「瑞士軍刀」，掌握其 Trie + Fail 指針 + 輸出鏈 三位一體的設計精髓，配合靜態陣列與輸出鏈迭代優化，即可輕鬆應對百萬級文本匹配挑戰。