洛谷B3927题：基于哈希表实现文章翻译
7个月前 (08-13)
一、题目解读
洛谷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;
}五、总结
该解法通过哈希表优化了字典查询效率，结合字符流分单词处理，实现了简洁且高效的翻译逻辑。关键点在于利用标点符号作为自然分隔符，避免了复杂的分词算法。对于大规模文本翻译，可进一步优化哈希表内存管理或采用更高效的数据结构。
原创内容 转载请注明出处
