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

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

4个月前 (08-13)

洛谷B3927题:基于哈希表实现文章翻译 GESP 哈希表 字典序 C++ GESP四级 第1张

一、题目解读

洛谷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;
}

五、总结

该解法通过哈希表优化了字典查询效率,结合字符流分单词处理,实现了简洁且高效的翻译逻辑。关键点在于利用标点符号作为自然分隔符,避免了复杂的分词算法。对于大规模文本翻译,可进一步优化哈希表内存管理或采用更高效的数据结构




原创内容 转载请注明出处

分享给朋友:

相关文章

IOI 1994 洛谷1216:如何用O(1)空间解决数字三角形问题?附代码实现

IOI 1994 洛谷1216:如何用O(1)空间解决数字三角形问题?附代码实现

题目重解:数字三角形是一个经典的动态规划问题,给定一个由数字组成的三角形结构,从顶部出发,每次可以移动到下方相邻的数字,最终到达底部。我们需要找到一条路径,使得路径上经过的数字总和最大。这个问题可以很...

2023年GESP四级小杨的字典(洛谷B3927)解题报告:基于哈希表的字符串替换优化

2023年GESP四级小杨的字典(洛谷B3927)解题报告:基于哈希表的字符串替换优化

一、题目解读题目要求实现一个“字典替换”功能:给定一个字典(键值对映射)和一段文本,将文本中出现的字典中的单词替换为其对应的值,未匹配的单词用“UNK”代替。需处理标点符号分隔单词,并确保输入异常情况...

洛谷P2190题解:铁路售票系统车厢计算(差分数组+前缀和优化)

洛谷P2190题解:铁路售票系统车厢计算(差分数组+前缀和优化)

一、题目解读洛谷P2190题要求解决铁路售票系统中的车厢数量计算问题。题目给定n个车站和m条订票申请,每条申请包含区间[x,y)及乘客数z。需要计算在不超载的情况下(每节车厢最多36人),满足所有乘客...

洛谷2652题解析:同花顺排序问题的动态规划与滑动窗口优化

洛谷2652题解析:同花顺排序问题的动态规划与滑动窗口优化

一、题目解读洛谷2652题要求对一组扑克牌进行排序,目标是找到最少需要调整的次数,使得所有牌形成同花顺。题目中,扑克牌由花色和数字组成,需先按花色排序,再在同花色内按数字排序。核心难点在于如何处理花色...

洛谷P1121题解:动态规划求解环形数组最大子段和问题(附代码注释)

洛谷P1121题解:动态规划求解环形数组最大子段和问题(附代码注释)

一、题目解读洛谷P1121题要求求解环形数组的最大子段和,即在一个环形数组中找到一个连续子段,使其元素和最大。环形数组的特殊性在于首尾元素可相连,需考虑线性子段与跨越首尾的环形子段两种情况。二、解题思...

力扣LCR074题区间合并算法解析:贪心排序与区间重叠处理

力扣LCR074题区间合并算法解析:贪心排序与区间重叠处理

一、题目解读力扣LCR074题要求对给定的二维区间数组(每个区间由起始点和终止点构成)进行合并,将重叠的区间合并为更宽的区间,最终输出不重叠的合并结果。例如,输入[[1,3],[2,6],[8,10]...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。