POJ 2503 Babelfish：字典翻譯與 Trie/Map 兩種解法

問題描述

給定最多 100,000 條字典條目，每條包含一個英文單詞與一個外語單詞（外語單詞不重複）。隨後給出一段最多 100,000 個外語單詞的信息。要求將信息翻譯為英文：若外語單詞在字典中存在，輸出對應英文；否則輸出 "eh"。單詞長度 ≤ 10，僅含小寫字母。

核心思路

本質是「鍵值映射」查找：外語單詞 → 英文單詞。數據量大（10 萬級），需 O(1) 或 O(L) 查找（L 為單詞長度）。兩種主流方案：

1. 哈希表：C++ unordered_map 或 map（紅黑樹，O(log N)）。
2. 字典樹：每個節點存儲子節點指針與對應英文單詞的索引，查找時間 O(L)，空間較優。

方案一：std::map 實現（代碼簡潔）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unordered_map<string, string> dict;  // 或 map
    string foreign, english;
    // 讀取字典部分（以空行分隔）
    while (getline(cin, foreign)) {
        if (foreign.empty()) break;
        stringstream ss(foreign);
        ss >> english >> foreign;
        dict[foreign] = english;
    }
    // 翻譯信息
    while (cin >> foreign) {
        auto it = dict.find(foreign);
        if (it != dict.end()) cout << it->second << '\n';
        else cout << "eh\n";
    }
    return 0;
}

注意：輸入量大，建議關閉同步並使用 scanf/printf 或 fast I/O。

方案二：字典樹實現（空間更優、查找確定性 O(L)）

節點結構

struct TrieNode {
    int idx;                 // 對應英文單詞在數組中的索引，-1 表示非單詞結尾
    TrieNode* next[26];
    TrieNode() : idx(-1) { memset(next, 0, sizeof(next)); }
};

插入與查找

vector<string> eng;  // 存儲英文單詞，下標即 idx

void insert(TrieNode* root, const char* s, int id) {
    TrieNode* p = root;
    for (int i = 0; s[i]; ++i) {
        int c = s[i] - 'a';
        if (!p->next[c]) p->next[c] = new TrieNode();
        p = p->next[c];
    }
    p->idx = id;
}

int query(TrieNode* root, const char* s) {
    TrieNode* p = root;
    for (int i = 0; s[i]; ++i) {
        int c = s[i] - 'a';
        if (!p->next[c]) return -1;
        p = p->next[c];
    }
    return p->idx;
}

主流程

int main() {
    TrieNode* root = new TrieNode();
    char buf[20];
    int id = 0;
    // 讀字典
    while (scanf("%s", buf) == 1) {
        string foreign(buf);
        if (foreign == "") break;  // 實際以空行分隔，scanf 讀不到空行，需用 gets/fgets
        string english;
        scanf("%s", buf);
        english = buf;
        eng.push_back(english);
        insert(root, foreign.c_str(), id++);
    }
    // 讀信息並翻譯
    while (scanf("%s", buf) == 1) {
        int idx = query(root, buf);
        if (idx != -1) printf("%s\n", eng[idx].c_str());
        else printf("eh\n");
    }
    return 0;
}

實際比賽中常用 gets 逐行讀取，解析空行分隔。

兩種方案對比

總結

POJ 2503 是典型的「字典查找」問題。unordered_map 寫法最快、最不易出錯，適合比賽現場；字典樹則展示了字符串專用數據結構的優勢，適合進階練習或對空間/最壞情況敏感的場景。