伊格纳修斯真是走了狗屎运，昨天居然遇到了火星人！可惜他完全听不懂火星人的语言。临走时，火星人给了他一本火星历史书和一本词典。现在伊格纳修斯想把这本历史书翻译成英语，你能帮帮他吗？
输入
本题只有一组测试数据，包含两个部分：词典部分和书籍部分。词典部分以一行字符串 "START" 开头，这行要忽略，接下来是若干行，每行包含两个字符串，第一个是英语单词，第二个是对应的火星语单词。当遇到一行只有 "END" 时，词典部分结束，这行也要忽略。书籍部分同样以一行 "START" 开头，忽略这行，接着是一篇用火星语写的文章。你需要用词典把文章翻译成英语：如果词典里有对应的单词，就翻译成英语；找不到的单词就原样保留。空格(' ')、制表符('\t')、换行符('\n')以及所有标点符号都不翻译。遇到一行只有 "END" 时，书籍部分结束，输入也结束。所有单词均为小写，单词长度最多10个字符，每行最多3000个字符。
输出
你需要输出这本历史书的英文翻译版本。
示例
| Input复制 | Output复制 |
|---|---|
START from fiwo hello difh mars riwosf earth fnnvk like fiiwj END START difh, i'm fiwo riwosf. i fiiwj fnnvk! END | hello, i'm from mars. i like earth! |
提示
输入量巨大，建议使用 scanf 来读入。
题目分析
本题的核心诉求是实现一个海量单词的映射翻译系统。给定一部火星文到英文的词典，要求将一段火星文历史书翻译成英文。
题目的难点和核心约束在于文本格式的绝对保留： 翻译过程中，必须原封不动地保留原文本中的所有标点符号、空格、制表符和换行符。这决定了我们不能使用常规的cin>>string或stringstream按空格分割来读取历史书部分，否则会丢失重要的排版信息和紧贴单词的标点符号。
思考过程与解题思路
数据结构选择：
std::mapvs 字典树虽然 STL的map<string,string>或unordered_map可以快速实现映射，但本题输入量巨大（多达数千个单词，且查表极为频繁）。map的底层红黑树常数较大，容易导致超时。因此，采用静态数组实现的字典树是时空效率最优的解法。 建树逻辑：因为要用火星文查英文，所以将火星文作为树的路径进行插入，在单词结束的叶子节点上存储对应的英文翻译。输入流处理：切割还是逐字符遍历？如果尝试先按照标点符号切割单词，逻辑会非常繁琐，且极易漏掉连续标点或多重空格。 最优的破局点是状态机思维（逐字符读取）： 一段文本本质上是由“字母”和“非字母（标点/空白）”交替组成的。我们只需要逐个读取字符（
cin.get()）：遇到字母：存入临时缓冲区（拼接成火星文单词）。
遇到非字母：说明一个单词刚刚结束。此时拿着缓冲区里的单词去字典树查询翻译并输出，然后清空缓冲区，最后原样输出这个非字母字符。
算法设计
静态字典树构建：
声明结构体数组
tree[500000]，利用全局变量天然初始化为0的特性，省去memset的开销。结构体包含
next[26]（指向子节点）、flag（标记是否为单词结尾）和s3（存储英文释义）。
读入词典： 通过
while(cin>>s1>>s2)循环读取，遇到"END"结束。调用insert(s1, s2)完成映射构建。清空输入流残存边界： 读完词典的最后一行
"END"后，输入流缓冲区中还会残留一个换行符\n。必须通过cin.get()将其吞掉，以免干扰后续的正文读取。正文翻译与状态机处理： 使用
while (cin.get(ch))逐字节读取。若为小写字母，追加到字符串
s4。若为非小写字母（且不是结束符
E），触发结算机制：查询s4，输出结果，清空s4，并输出当前非字母符号。
时空复杂度分析
时间复杂度：
建树阶段：插入一个单词的复杂度为O(L)，L为单词长度。总时间复杂度为
。
翻译阶段：历史书逐字符读取，每构成一个单词在字典树中查询的时间为O(L)。整体翻译时间复杂度严格线性，为O(历史书总字符数)。整体复杂度完全足以应对海量输入。
空间复杂度： 静态字典树最多需要开辟节点总数×26个指针空间。本题开辟十万级数组
tree[500000]，空间消耗低于常见的65MB限制。空间复杂度为 O(N⋅∣Σ∣)，其中N为最大节点数，∣Σ∣=26。
坑点总结
I/O同步机制与
getchar冲突： 代码中使用了ios::sync_with_stdio(false); cin.tie(0);解除了C++与C的I/O同步。一旦解除同步，绝对不能再混用scanf或getchar，否则会导致缓冲区错乱。必须全程使用cin或cin.get()。流缓冲区的换行符残留：
cin>>在读取完毕后，会把空格或换行符留在缓冲区。在切换为cin.get()读取正文前，必须先吃掉这个残存的换行符。结束符的高效判定： 题目明确指出历史书部分所有单词均为小写。因此，遇到大写字母
E（来自结尾的END）即可直接判定正文结束，这是一种取巧且高效的剪枝。
完整代码
#include <iostream> #include <string> using namespace std; struct treenode{ int next[26];//状态转移表：记录通往26个小写字母子节点的编号 int flag;//标记到当前结点为止能否构成一个完整的单词 string s3;//记录到当前为止如果能构成一个单词 单词对应的英文 }tree[500000]; int pc;//内存池分配计数器，初始为0，0号节点作为树的根节点 //构造字典树 s1是英文 s2是火星文 //使用引用传参，避免字符串深拷贝的开销 void insert(string &s1,string &s2){ int p=0;//始终从根节点出发 //获取火星文s2的长度 int len=s2.size(); //遍历火星文的每个字符，搭建路径 for(int i=0;i<len;i++){ int j=s2[i]-'a'; //如果该通道尚未开辟，分配新节点编号 if(tree[p].next[j]==0){ tree[p].next[j]=++pc; } //指针跃迁到子节点 p=tree[p].next[j]; } //路径走完，在最后一个节点上存入英文释义，并打上完整单词标记 tree[p].s3=s1; tree[p].flag=1; } //查询 在字典树中查找火星文单词 int find(string &s4){ int p=0; //火星文单词的长度 int len=(int)s4.size(); //查找路径 for(int i=0;i<len;i++){ int j=s4[i]-'a'; if(tree[p].next[j]==0) return 0; p=tree[p].next[j]; } //如果当前能构成一个单词 输出这个单词 if(tree[p].flag==1){ cout<<tree[p].s3; return 1; } else return 0; } int main(){ //使用后严禁使用scanf,printf,getchar等c函数 ios::sync_with_stdio(false); cin.tie(0); string s; cin>>s;//存储第一个START string s1,s2; //第一部分 英文火星文词典部分 while(cin>>s1>>s2){ //通过END来判断词典部分的结束 if(s1!="END"&&s2!="START"){ //构造字典树 s1是英文 s2是火星文 //因为要翻译火星文 所以需要构造火星文字典树 insert(s1,s2); } else break; } //吃掉start后面的换行 不然就会导致第一个ch读入一个换行 cin.get();//不能用getchar（） 因为使用了ios：：sync //第二部分 历史书部分 char ch; string s4;//临时容器，用于拼接火星文字母 //逐个字符读取 不能用scanf 因为用了ios::sync //也不能用cin cin不会读空格、换行 while(cin.get(ch)){ //通过END来判断历史书的结束 题目已经告知所有单词均为小写 //所以我们判断一个E即可 if(ch!='E'){ //判断ch是否为字母 如果为字母就拼接到s4里 if(ch-'a'>=0&&ch-'a'<=25) s4+=ch; //如果不是字母就对s4（火星文）去字典树进行查找 //如果存在对应英文就输出英文 否则原样输出s4(火星文) //然后清空s4 并直接输出这一次的ch(非字母） else{ //如果查找到了s4对应的英文就输出英文(find函数直接输出了） //否则就原样输出 if(!find(s4)) cout<<s4; //原样输出当前这个非字母的符号 cout<<ch; //清空容器 准备拼接下一个单词 s4.clear(); } } //如果是END 就要退出了 else break; } return 0; }
