HDU 1251 統計難題：字典樹實現詞頻統計

問題描述

輸入包含兩個階段：第一階段讀入多行單詞（以空行結束），構建詞典；第二階段讀入查詢單詞，輸出每個單詞在詞典中出現的次數。單詞僅包含小寫字母，長度 ≤ 10。

字典樹結構

• 每個節點包含 cnt（以此節點結尾的單詞數）和 next[26] 子節點指針。
• 插入時沿字符遍歷，缺失節點則創建，最後節點 cnt++。
• 查詢時沿字符遍歷，若中途斷開返回 0，否則返回終點 cnt。

輸入處理技巧

使用 gets(s) 讀整行。第一階段：while (gets(s) && strlen(s)) insert(root, s); 空行結束。第二階段：while (gets(s)) printf("%d\n", find(root, s)); 直到 EOF。

完整代碼 (C++)

#include <cstdio>
#include <cstring>
char s[15];
struct node {
    int cnt;
    node *next[26];
    void init() {
        cnt = 0;
        for (int i = 0; i < 26; i++) next[i] = NULL;
    }
};
void insert(node *root, char *s) {
    node *p = root;
    for (int i = 0; s[i]; i++) {
        int t = s[i] - 'a';
        if (p->next[t] == NULL) {
            p->next[t] = new node;
            p = p->next[t];
            p->init();
        } else p = p->next[t];
        p->cnt++;
    }
}
int find(node *root, char *s) {
    node *p = root;
    for (int i = 0; s[i]; i++) {
        int t = s[i] - 'a';
        p = p->next[t];
        if (!p) return 0;
    }
    return p->cnt;
}
int main() {
    node *root = new node();
    root->init();
    while (gets(s) && strlen(s)) insert(root, s);
    while (gets(s)) printf("%d\n", find(root, s));
    return 0;
}

要點總結

• 字典樹適用於大量字符串的前綴查詢與統計。
• 注意內存釋放（競賽中通常忽略）。
• 輸入控制是本題關鍵難點。