HDU 4287 Intelligent IME：字典樹優化（數字串建樹 + 單詞映射查詢）

問題描述

手機九鍵鍵盤輸入數字串（2~9），每個數字對應 3~4 個字母。給定 N ≤ 5000 個數字串（長 ≤ 6）和 M ≤ 5000 個單詞（長 ≤ 6），求每個數字串能匹配多少單詞。匹配規則：單詞按鍵盤映射轉為數字串，完全相等則匹配。

優化關鍵：反向建樹

初始想法：建單詞 Trie，對每個數字串 DFS 枚舉所有可能字母組合查詢 → 爆炸（每位 3~4 選擇，長度 6 → 4^6=4096，N=5000 → 2×10^7，還可接受但常數大）。
優化：建數字串 Trie（N 棵，共用前綴），將每個單詞映射為其對應數字串，直接在數字串 Trie 中查詢 → O(單詞長度) 單次查詢，總 O(M·L) ≈ 3×10^4，極快。

映射函數

char to_digit(char c) {
    if (c >= 'a' && c <= 'c') return '2';
    if (c >= 'd' && c <= 'f') return '3';
    if (c >= 'g' && c <= 'i') return '4';
    if (c >= 'j' && c <= 'l') return '5';
    if (c >= 'm' && c <= 'o') return '6';
    if (c >= 'p' && c <= 's') return '7';
    if (c >= 't' && c <= 'v') return '8';
    return '9';  // w,x,y,z
}

代碼實現

struct TrieNode {
    int id;  // 該數字串的編號 (1~N)，0 表示非終結
    TrieNode* next[10];
    TrieNode(): id(0) { memset(next, 0, sizeof(next)); }
};

void insert(TrieNode* root, const string& s, int id) {
    TrieNode* p = root;
    for (char ch : s) {
        int d = ch - '0';
        if (!p->next[d]) p->next[d] = new TrieNode();
        p = p->next[d];
    }
    p->id = id;
}

int query(TrieNode* root, const string& s) {
    TrieNode* p = root;
    for (char ch : s) {
        int d = ch - '0';
        if (!p->next[d]) return 0;
        p = p->next[d];
    }
    return p->id;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N, M; cin >> N >> M;
        TrieNode* root = new TrieNode();
        vector num_strs(N+1);
        for (int i = 1; i <= N; ++i) {
            cin >> num_strs[i];
            insert(root, num_strs[i], i);
        }
        vector ans(N+1, 0);
        string word;
        for (int i = 0; i < M; ++i) {
            cin >> word;
            string mapped;
            for (char c : word) mapped += to_digit(c);
            int id = query(root, mapped);
            if (id) ans[id]++;
        }
        for (int i = 1; i <= N; ++i) cout << ans[i] << '\n';
        // 釋放 Trie 內存（遞歸 delete）
    }
    return 0;
}

複雜度

• 構建數字串 Trie：O(N·L) ≤ 5000×6 = 3×10^4。
• 單詞映射 + 查詢：O(M·L) ≤ 3×10^4。
• 總時間極快，內存：Trie 節點 ≤ 總數字串長度 ≤ 3×10^4。

關鍵點

1. 反向思維：建「查詢對象」的索引，而非「被查詢對象」的索引。
2. 單詞 → 數字串映射確定性、單向、無歧義。
3. 數字串長度 ≤ 6，Trie 深度極小。