当前位置：首页 > GESP > 2023年GESP四级小杨的字典（洛谷B3927）解题报告：基于哈希表的字符串替换优化

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

1天前

一、题目解读

题目要求实现一个“字典替换”功能：给定一个字典（键值对映射）和一段文本，将文本中出现的字典中的单词替换为其对应的值，未匹配的单词用“UNK”代替。需处理标点符号分隔单词，并确保输入异常情况的容错性。问题核心在于高效查找替换与字符边界处理。

二、解题思路

1. 哈希表优化：使用unordered_map存储字典，实现O(1)平均时间复杂度的查找，避免线性扫描。

2. 标点符号处理：自定义isPunctuation函数通过预定义字符串常量快速判断标点，减少字符遍历开销。

3. 流优化：通过ios::sync_with_stdio(false)和cin.tie(nullptr)禁用同步，提升输入效率。

4. 边界处理：利用current变量累积单词，遇到标点或末尾时触发替换，确保完整处理所有单词。

三、解题步骤

1. 初始化：读取字典数量N，创建unordered_map，循环处理键值对存入字典。

2. 输入清理：使用cin.ignore()清除换行符，确保getline正确读取后续文本。

3. 单词分段：遍历文本字符，若为标点则分割当前单词并替换（存在则替换，不存在则"UNK"），标点直接输出；若为字母则累积至current。

4. 末尾处理：文本末尾可能存在未处理的单词，需额外检查并替换。

5. 输出结果：拼接处理后的字符串并输出。

四、代码和注释

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

// 优化后的标点符号判断函数
bool isPunctuation(char c) {
    static const string punct = "!()-.[].{}\\|;:'\",./?<>";
    return punct.find(c)!= string::npos; // 利用预定义字符集快速查找
}

int main() {
    ios::sync_with_stdio(false); // 禁用流同步，加速输入
    cin.tie(nullptr); // 解除cin与cout绑定

    int N; // 字典条目数
    cin >> N;
    unordered_map<string, string> dict; // 创建哈希表字典
    
    // 读取字典，处理可能的输入异常
    for (int i = 0; i < N; ++i) {
        string a, b; // 键和值
        cin >> a >> b; // 可能存在空格或格式错误，但此处未做额外检查
        if (!a.empty()) dict[a] = b; // 过滤空键，避免无效条目
    }
    
    cin.ignore(); // 清除输入缓冲中的换行符（如最后一个条目后的换行）
    string s; // 待处理文本
    getline(cin, s); // 读取整行文本
    
    string result, current; // 结果串和当前累积单词
    for (size_t i = 0; i < s.size(); ++i) {
        char c = s[i];
        if (isPunctuation(c)) { // 遇到标点
            // 处理当前单词
            if (!current.empty()) {
                auto it = dict.find(current); // 哈希查找
                result += (it!= dict.end())? it->second : "UNK"; // 替换或"UNK"
                current.clear(); // 清空当前单词
            }
            result += c; // 添加标点至结果
        } else { // 非标点字符（字母或数字）
            current += c; // 累积至单词
        }
    }
    
    // 处理末尾剩余单词（如文本以单词结尾）
    if (!current.empty()) {
        auto it = dict.find(current);
        result += (it!= dict.end())? it->second : "UNK";
    }
    
    cout << result << endl; // 输出最终结果
    return 0;
}