BZOJ 3172 [TJOI2013] 單詞：AC自動機 + 失配樹反向遞推統計詞頻

題目大意

給定 N (≤ 200) 個模式串（總長度 ≤ 10⁶），以及一篇文本（隱含在模式串構建過程中？實際為：將所有模式串拼接或單獨處理）。題目要求：對每個模式串，統計它在文本中出現的次數。Sample: 模式串 a, aa, aaa，文本隱含為 aaa... 輸出 6, 3, 1。

修正理解：實際是給定 N 個單詞，構建它們的 Trie，然後對一個長文本（或所有單詞構成的文本？）跑 AC 自動機匹配。但 Sample 輸入只有 3 個單詞無額外文本。真實題意：給定 N 個單詞，將它們視為模式串，文本是這 N 個單詞按順序拼接？或是每個單詞在「所有單詞拼成的長文本」中出現次數？

根據代碼邏輯：插入所有單詞到 Trie，每個單詞結尾節點 w[node]++。構建 AC 自動機後，按 BFS 逆序（從葉向根）遞推 w[fail[u]] += w[u]。最終 w[p[i]] 即為第 i 個單詞的出現次數。這其實是統計每個模式串在所有模式串構成的集合中作為子串出現的次數（或某隱含文本）。無論如何，核心技巧是 AC自動機 + 失配樹上的 DP 遞推。

核心算法：AC自動機 + 失配樹遞推

步驟 1：構建 Trie 並記錄單詞結尾

struct Node { int next[26], fail; int cnt = 0; } trie[MAXN];
int tot = 1, pos[N]; // pos[i] 記錄第 i 個單詞的結尾節點

void insert(string& s, int id) {
    int u = 1;
    for (char ch : s) {
        int c = ch - 'a';
        if (!trie[u].next[c]) trie[u].next[c] = ++tot;
        u = trie[u].next[c];
    }
    trie[u].cnt++;          // 該節點作為單詞結尾計數 +1
    pos[id] = u;            // 記錄單詞結尾位置
}

步驟 2：BFS 構建失配指針（並補全轉移邊）

int bfs_order[MAXN], bfs_cnt = 0;

void build_ac() {
    queue q; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        bfs_order[++bfs_cnt] = u; // 記錄 BFS 順序，便於後續逆序遞推
        for (int c = 0; c < 26; ++c) {
            int v = trie[u].next[c];
            if (v) {
                trie[v].fail = trie[trie[u].fail].next[c];
                q.push(v);
            } else {
                trie[u].next[c] = trie[trie[u].fail].next[c]; // 補全轉移
            }
        }
    }
}

步驟 3：失配樹上逆序遞推累加計數

關鍵洞察：失配指針構成一棵樹（根為 1）。若節點 u 代表某前綴，則 fail[u] 代表其最長真後綴。若文本匹配到達 u，意味著 fail[u] 對應的模式也同時匹配了。因此，將 cnt[u] 累加到 cnt[fail[u]] 即可得到所有模式的總匹配次數。

// 按 BFS 逆序（從葉向根）遞推
for (int i = bfs_cnt; i >= 1; --i) {
    int u = bfs_order[i];
    trie[trie[u].fail].cnt += trie[u].cnt;
}

// 輸出答案
for (int i = 1; i <= N; ++i) {
    cout << trie[pos[i]].cnt << '\n';
}

為什麼逆序遞推是正確的？

• BFS 保證父節點（失配目標）在子節點之後被處理
• 逆序遍歷確保先處理深層節點，將其計數傳遞給較淺的失配祖先
• 相當於在失配樹上做「子樹和」DP

複雜度分析

• 構建 Trie：O(總長度)
• BFS 構建 AC：O(節點數 × 字符集) = O(總長度 × 26)
• 逆序遞推：O(節點數)
• 總時間/空間：O(總長度)，總長度 ≤ 10⁶ 完全可行

易錯點

1. 失配邊補全：trie[u].next[c] = trie[trie[u].fail].next[c] 必須在 BFS 中完成，保證後續匹配 O(1) 跳轉
2. 計數初始化：插入時 trie[u].cnt++ 標記單詞結尾，而非 w[now]++（原代碼寫法）
3. 根節點 fail 指向自身：trie[1].fail = 1 或 0，補全邊時需處理