HDU 1251 統計難題：字典樹與 Map 兩種實現

題目大意

給定一組單詞（僅小寫字母，長度 ≤ 10，無重複），以空行結束。隨後為一系列查詢字串，對每個查詢輸出以該字串為前綴的單詞數量（單詞本身也是自己的前綴）。單組測試資料，讀至 EOF。

樣例

輸入：
banana
band
bee
absolute
acm

ba
b
band
abc

輸出：
2
3
1
0

解法一：字典樹

構建 Trie，每個節點記錄以該前綴結尾的單詞數。插入單詞時沿路徑 sum++，查詢時走到查詢字串末端節點，返回其 sum。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 400000 + 10;

struct Trie {
    int sz;
    int ch[MAXN][26];
    int sum[MAXN];
    Trie() { sz = 1; memset(ch, 0, sizeof(ch)); memset(sum, 0, sizeof(sum)); }
    int idx(char c) { return c - 'a'; }
    void insert(const char *s) {
        int u = 0, n = strlen(s);
        for (int i = 0; i < n; ++i) {
            int c = idx(s[i]);
            if (!ch[u][c]) ch[u][c] = sz++;
            u = ch[u][c];
            sum[u]++;
        }
    }
    int query(const char *s) {
        int u = 0, n = strlen(s);
        for (int i = 0; i < n; ++i) {
            int c = idx(s[i]);
            if (!ch[u][c]) return 0;
            u = ch[u][c];
        }
        return sum[u];
    }
};

int main() {
    Trie trie;
    char buf[20];
    while (scanf("%s", buf) == 1) {
        if (buf[0] == '\0') break;
        trie.insert(buf);
    }
    while (scanf("%s", buf) == 1) {
        printf("%d\n", trie.query(buf));
    }
    return 0;
}

解法二：Map 統計所有前綴

讀入單詞時，枚舉其所有前綴（含自身），在 map<string, int> 中計數。查詢直接查表。

#include <cstdio>
#include <map>
#include <string>
#include <iostream>
using namespace std;

map<string, int> mp;
string s;

int main() {
    char ch;
    while (true) {
        scanf("%c", &ch);
        if (ch == ' ') { scanf("%c", &ch); s = ""; }
        s += ch;
        if (ch == ' ') break;
        mp[s]++;
    }
    while (cin >> s) {
        printf("%d\n", mp[s]);
    }
    return 0;
}

比較與總結

• 字典樹：空間較省，查詢 O(L)，適合大量單詞、長前綴。
• Map：實現簡單，利用 STL，但儲存所有前綴空間較大。
• 本題單詞長度 ≤ 10，兩種方法均能 AC。