csp信奥赛C++高频考点专项训练之字符串 --【子串查找】：小杨的字典-平芜编程栈

csp信奥赛C++高频考点专项训练之字符串 --【子串查找】：小杨的字典

题目描述

在遥远的星球，有两个国家 A 国和 B 国，他们使用着不同的语言：A 语言和 B 语言。小杨是 B 国的翻译官，他的工作是将 A 语言的文章翻译成 B 语言的文章。

为了顺利完成工作，小杨制作了一本字典，里面记录了N NN个 A 语言单词对应的 B 语言单词，巧合的是，这些单词都由地球上的 26 个小写英文字母组成。

小杨希望你写一个程序，帮助他根据这本字典翻译一段 A 语言文章。这段文章由标点符号!()-[]{}\|;:'",./?<>和一些 A 语言单词构成，每个单词之间必定由至少一个标点符号分割，你的程序需要把这段话中的所有 A 语言单词替换成它的 B 语言翻译。特别地，如果遇到不在字典中的单词，请使用大写 UNK 来替换它。

例如，小杨的字典中包含2 22个 A 语言单词abc和d，它们的 B 语言翻译分别为a和def，那么我们可以把 A 语言文章abc.d.d.abc.abcd.翻译成 B 语言文章a.def.def.a.UNK.其中，单词abcd不在词典内，因此我们需要使用 UNK 来替换它。

输入格式

第一行一个整数N NN，表示词典中的条目数。保证N ≤ 100 N \le 100N≤100。

接下来N NN行，每行两个用单个空格隔开的字符串A AA，B BB,分别表示字典中的一个 A 语言单词以及它对应的 B 语言翻译。保证所有A AA不重复；保证A AA和B BB的长度不超过10 1010。

最后一行一个字符串S SS，表示需要翻译的 A 语言文章。保证字符串S SS的长度不超过1000 10001000，保证字符串S SS只包含小写字母以及标点符号!()-[]{}\|;:'",./?<>。

输出格式

输出一行，表示翻译后的结果。

输入输出样例 1

输入 1

2 abc a d def abc.d.d.abc.abcd

输出 1

a.def.def.a.UNK

输入输出样例 2

输入 2

3 abc a d def abcd xxxx abc,(d)d!-abc?abcd

输出 2

a,(def)def!-a?xxxx

输入输出样例 #3

输入 3

1 abcdefghij klmnopqrst !()-[]{}\|;:'",./?<>abcdefghijklmnopqrstuvwxyz

输出 3

!()-[]{}\|;:'",./?<>UNK

这道题用 STL 的map就能搞定，核心思路是“逐字符扫描 + 单词缓存”。

思路分析

建立词典映射：用一个map<string, string>来存储 A 语言单词和 B 语言翻译的对应关系，便于快速查找。
逐字扫描：从头到尾遍历待翻译的文章s。
- 如果当前字符是字母，就把它追加到一个临时的word字符串里，用来拼接出一个完整的单词。
- 如果遇到标点符号，说明前面的单词已经结束，此时需要去词典里查word。如果查到了，就把它的翻译加到结果里；否则就添加"UNK"。接着，再把这个标点符号本身也添加到结果中，并清空word。
处理末尾：文章扫描完成后，还要检查一下word是否还有内容，有的话就按规则处理，避免遗漏最后一个单词。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){// 建立 A 语言到 B 语言的映射词典map<string,string>mp;intn;cin>>n;string a,b;// 读入 N 个单词对for(inti=0;i<n;i++){cin>>a>>b;mp[a]=b;// 存储映射关系}string s,t="",ans="";cin>>s;// 读入待翻译文章// 逐字符扫描文章for(inti=0;i<(int)s.size();i++){// 当前字符是小写字母，将其添加到临时单词中if(s[i]>='a'&&s[i]<='z'){t+=s[i];}else{// 遇到标点符号，触发单词处理// 如果临时单词非空，说明一个单词收集完毕if(t!=""){// 查询词典，找到则输出翻译，否则输出 "UNK"if(mp.count(t))ans+=mp[t];elseans+="UNK";t="";// 清空临时单词，准备下一个}// 标点符号本身也要保留ans+=s[i];}}// 处理文章末尾可能遗留的最后一个单词if(t!=""){if(mp.count(t))ans+=mp[t];elseans+="UNK";}// 输出最终结果cout<<ans<<endl;return0;}

【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

csp信奥赛C++高频考点专项训练之字符串 --【子串查找】：小杨的字典