HDU 2846 Repository：字典樹統計子串出現次數

問題描述

給 P (≤10000) 個小寫單詞（長≤20），Q (≤100000) 次查詢，每次給一個串，問有多少個單詞包含它作為子串。

字典樹方案

將每個單詞的所有子串插入字典樹，節點記錄 cnt（有多少不同單詞經過此節點）和 last（最後插入的單詞編號），避免同一單詞重複計數。

核心代碼

struct Trie {
    int cnt, last;
    Trie* next[26];
    Trie(): cnt(0), last(0) { memset(next, 0, sizeof(next)); }
};

void insert(Trie* root, const char* s, int id) {
    for (int i = 0; s[i]; ++i) {
        Trie* p = root;
        for (int j = i; s[j]; ++j) {
            int c = s[j]-'a';
            if (!p->next[c]) p->next[c] = new Trie();
            p = p->next[c];
            if (p->last != id) { p->last = id; ++p->cnt; }
        }
    }
}

int query(Trie* root, const char* s) {
    Trie* p = root;
    for (int i = 0; s[i]; ++i) {
        int c = s[i]-'a';
        if (!p->next[c]) return 0;
        p = p->next[c];
    }
    return p->cnt;
}

複雜度分析

• 構建：P 個單詞，每長度 L ≤ 20，子串數 O(L²)，總操作 ≤ 10000×400 = 4×10⁶，極快。
• 查詢：O(|query|)，總長 ≤ 3×10⁶。
• 內存：節點數 ≤ 總子串長度 ≈ 4×10⁶，每節點 ~108 字節，約 400MB，接近限制。優化：用靜態數組池、壓縮字典樹或後綴自動機 (SAM) 更省內存。

優化建議

1. 改用後綴自動機 (SAM) 線性構建，空間 O(總長度)。
2. 或將所有單詞用特殊分隔符拼成一個大串，建廣義後綴自動機/後綴數組。
3. 本題數據較弱，字典樹配合內存池通常能過。