G4005 [GESP202312 四级] 小杨的字典 题解

知识点：字符串解析、映射、模拟。

解题思路

用映射记录词典，扫描句子时累积连续小写字母；遇分隔符时查词输出译文或UNK，并原样输出分隔符。末尾再处理最后一个词。

为什么正确

每段连续字母恰被查表一次，分隔字符未变且顺序不变，得到逐词翻译。

易错点

句子末尾可能没有分隔符；未知词输出UNK，不能漏掉标点。

复杂度

设总长度L、词条数n，时间O(L log n)上界，空间O(词典与输入长度)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    map<string,string>d;
    while(n--) {
        string a,b;
        cin>>a>>b;
        d[a]=b;
    }
    string s,w;
    cin>>s;
    auto flush=[&]() {
        if(w.size()) {
            cout<<(d.count(w)?d[w]:"UNK");
            w.clear();
        }
    }
    ;
    for(char c:s) {
        if(c>='a'&&c<='z')w+=c;
        else {
            flush();
            cout<<c;
        }
    }
    flush();
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。