HDU 1251 統計難題——Trie 字典樹統計前綴出現次數

問題描述

輸入若干單詞（每行一個，空行結束），然後若干查詢單詞。對每個查詢，輸出字典中以該單詞為前綴的單詞數量。單詞長度 ≤ 10，小寫字母。內存限制較大。

Trie 字典樹

• 節點：`next[26]` 子節點指針，`cnt` 經過此節點的單詞數（即以此節點路徑為前綴的單詞數）。
• 插入：逐字符走/建節點，每經過一個節點 `cnt++`。
• 查詢：逐字符走，若中途缺節點返回 0；走完返回當前節點 `cnt`。

代碼實現

#include 
using namespace std;

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

Trie* root = new Trie();

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while (getline(cin, s) && !s.empty()) insert(s.c_str());
    while (getline(cin, s)) cout << query(s.c_str()) << '\n';
    return 0;
}

關鍵點

• 字符集固定 26 小寫：數組 `next[26]` 比 `map/unordered_map` 快得多。
• cnt 統計前綴數：插入時每節點 `++cnt`，查詢直接返回尾節點 `cnt`，無需遍歷子樹。
• 內存池優化：題目內存大，`new` 足夠；極限情況可預分配節點數組 `Trie nodes[maxNodes]`，用指針/索引管理。
• 輸入讀取：`getline` 讀整行，空行分隔插入/查詢階段。

複雜度

• 插入：O(總字符數)。
• 查詢：O(查詢單詞長度) = O(10)。
• 空間：O(總字符數) 節點數。

總結

Trie 樹經典應用：前綴計數。節點存 `cnt` 即以該前綴為前綴的單詞數，插入時累加，查詢 O(L) 直接返回。代碼極簡，內存足夠時直接 `new` 節點最省事。