What Are You Talking About（HDU- P1075）

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