当前位置：首页 > GESP > 洛谷B3927题：基于哈希表实现文章翻译

洛谷B3927题：基于哈希表实现文章翻译

19小时前

一、题目解读

洛谷B3927题要求实现一个简单的翻译系统：给定A语言到B语言的字典映射，以及一篇A语言文章，需要将文章中的每个单词替换为字典中对应的B语言单词。若字典中不存在该单词，则用"UNK"代替。题目核心在于高效处理字符串分单词、字典查询及标点符号的保留。

二、解题思路

1. 哈希表映射：使用unordered_map<string, string> dictionary存储A语言到B语言的单词映射，支持O(1)查询效率。

2. 分单词处理：遍历文章字符流，利用标点符号作为分隔符，将连续的非标点字符组成单词，再进行字典查找。

3. 未知词处理：若单词未在字典中，统一输出"UNK"保证翻译完整性。

4. 标点保留：遇到标点符号时直接添加到结果串，确保翻译后文章格式不变。

三、解题步骤

1. 输入参数：读取字典条目数N，循环N次输入A语言单词a和B语言翻译b，存入字典。

2. 处理文章：逐字符遍历输入的文章，根据是否标点符号执行不同逻辑。

3. 单词积累：非标点字符时，拼接至currentWord；遇标点或文章末尾时，查询字典并输出结果。

4. 结果输出：最终拼接完成的翻译结果打印。

四、代码与注释

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

// 判断字符是否为标点符号
bool isPunctuation(char c) {
    return c < 'a' || c > 'z'; // 仅考虑小写字母外的字符为标点
}

int main() {
    long long N;
    cin >> N; // 输入字典条目数
    
    // 创建字典，存储A语言到B语言的映射
    unordered_map<string, string> dictionary;
    
    // 读取字典条目
    for (int i = 0; i < N; i++) {
        string a, b;
        cin >> a >> b; // 输入A单词和对应B翻译
        dictionary[a] = b; // 存入哈希表
    }
    
    string article, result; // 原文章和翻译结果
    cin >> article; // 输入待翻译文章
    
    string currentWord; // 当前正在处理的单词
    for (char c : article) {
        if (isPunctuation(c)) {
            // 遇到标点符号，处理当前单词
            if (!currentWord.empty()) {
                // 查找字典
                if (dictionary.count(currentWord)) {
                    result += dictionary[currentWord];
                } else {
                    result += "UNK"; // 未知单词替换
                }
                currentWord.clear(); // 清空当前单词
            }
            result += c; // 添加标点符号至结果
        } else {
            // 非标点符号，添加到当前单词
            currentWord += c;
        }
    }
    
    // 处理文章末尾可能剩余的单词
    if (!currentWord.empty()) {
        if (dictionary.count(currentWord)) {
            result += dictionary[currentWord];
        } else {
            result += "UNK";
        }
    }
    
    cout << result << endl; // 输出翻译结果
    return 0;
}