題目大意

輸入一組單詞表（以空行結束），隨後多行查詢字符串。對每個查詢，輸出單詞表中以該字符串為前綴的單詞數量（單詞本身算作自己的前綴）。單詞僅含小寫字母，長度 ≤ 10，無重複。

Trie 結構設計

struct Node {
    int cnt;           // 以此節點為前綴的單詞數
    Node* child[26];   // 26 個小寫字母
    Node() : cnt(0) { memset(child, 0, sizeof(child)); }
};

• cnt 在插入時沿路遞增，查詢時直接返回終止節點的 cnt。
• 無需標記「是否為單詞結尾」，因題目只問前綴計數。

核心操作

void insert(const char* s) {
    Node* cur = root;
    for (int i = 0; s[i]; ++i) {
        int idx = s[i] - 'a';
        if (!cur->child[idx]) cur->child[idx] = new Node();
        cur = cur->child[idx];
        ++cur->cnt;
    }
}

int query(const char* s) {
    Node* cur = root;
    for (int i = 0; s[i]; ++i) {
        int idx = s[i] - 'a';
        if (!cur->child[idx]) return 0;
        cur = cur->child[idx];
    }
    return cur->cnt;
}

完整主程序

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    char buf[20];
    // 讀單詞表
    while (cin.getline(buf, 20)) {
        if (buf[0] == '\0') break;
        insert(buf);
    }
    // 處理查詢
    while (cin.getline(buf, 20)) {
        cout << query(buf) << '\n';
    }
    return 0;
}

關鍵細節

1. 輸入處理：gets 已棄用，用 cin.getline 或 fgets；空行判斷 buf[0]=='\0'。
2. 內存管理：競技編程中進程結束自動回收；工程代碼需遞歸釋放節點。
3. 複雜度：插入/查詢 O(L)，L ≤ 10，極快。空間 O(總字符數) ≤ 26·N。

變體延伸

• 支持刪除單詞：cnt--，若為 0 可遞歸釋放節點。
• 查詢最長公共前綴：遍歷 Trie 找第一個 cnt==1 或分支節點。
• 自動補全：DFS 收集前綴下所有單詞。

總結

HDU 1251 是 Trie 統計前綴計數的經典模板題。關鍵在於節點攜帶 cnt 字段，將「以此為前綴的單詞數」在插入時預計算，查詢時 O(1) 獲取。掌握 Trie 插入/查詢/釋放三部曲，應對字符串前綴問題游刃有餘。