csp信奥赛C++高频考点专项训练之字符串 --【子串查找】：[NOIP 2009 提高组] 潜伏者

csp信奥赛C高频考点专项训练之字符串 --【子串查找】[NOIP 2009 提高组] 潜伏者题目描述R 国和 S 国正陷入战火之中双方都互派间谍潜入对方内部伺机行动。历尽艰险后潜伏于 S 国的 R 国间谍小 C 终于摸清了 S 国军用密码的编码规则S 国军方内部欲发送的原信息经过加密后在网络上发送原信息的内容与加密后所得的内容均由大写字母A ∼ Z \texttt{A}\sim\texttt{Z}A∼Z构成无空格等其他字符S 国对于每个字母规定了对应的密字。加密的过程就是将原信息中的所有字母替换为其对应的密字每个字母只对应一个唯一的密字不同的字母对应不同的密字。密字可以和原字母相同。例如若规定A \tt AA的密字为A \tt AAB \tt BB的密字为C \tt CC其他字母及密字略则原信息A B A \tt ABAABA被加密为A C A \tt ACAACA。现在小 C 通过内线掌握了 S 国网络上发送的一条加密信息及其对应的原信息。小 C 希望能通过这条信息破译 S 国的军用密码。小 C 的破译过程是这样的扫描原信息对于原信息中的字母x xx代表任一大写字母找到其在加密信息中的对应大写字母y yy并认为在密码里y yy是x xx的密字。如此进行下去直到停止于如下的某个状态所有信息扫描完毕A ∼ Z \texttt{A}\sim\texttt{Z}A∼Z所有26 2626个字母在原信息中均出现过并获得了相应的密字所有信息扫描完毕但发现存在某个或某些字母在原信息中没有出现扫描中发现掌握的信息里有明显的自相矛盾或错误违反 S 国密码的编码规则。例如某条信息X Y Z \tt XYZXYZ被翻译为A B A \tt ABAABA就违反了“不同字母对应不同密字”的规则。在小 C 忙得头昏脑涨之际R 国司令部又发来电报要求他翻译另外一条从 S 国刚刚截取到的加密信息。现在请你帮助小 C通过内线掌握的信息尝试破译密码。然后利用破译的密码翻译电报中的加密信息。输入格式共三行每行为一个长度在1 11到100 100100之间的字符串。第一行为小 C 掌握的一条加密信息第二行为第一行的加密信息所对应的原信息第三行为 R 国司令部要求小 C 翻译的加密信息。输入数据保证所有字符串仅由大写字母A ∼ Z \texttt{A}\sim\texttt{Z}A∼Z构成且第一行长度与第二行相等。输出格式共一行。若破译密码停止时出现2 , 3 2,32,3两种情况请你输出F a i l e d \tt FailedFailed否则请输出利用密码翻译电报中加密信息后得到的原信息。输入输出样例 1输入 1AA AB EOWIE输出 1Failed输入输出样例 2输入 2QWERTYUIOPLKJHGFDSAZXCVBN ABCDEFGHIJKLMNOPQRSTUVWXY DSLIEWO输出 2Failed输入输出样例 3输入 3MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL FLSO输出 3NOIP说明/提示【输入输出样例一说明】原信息中的字母A \tt AA和B \tt BB对应相同的密字输出F a i l e d \tt FailedFailed。【输入输出样例二说明】字母Z \tt ZZ在原信息中没有出现输出F a i l e d \tt FailedFailed。思路分析题目要求根据已知的加密信息第一行和对应的原信息第二行推导出一个从原字母到密字加密后的字母的双射映射。如果推导过程中出现矛盾同一个原字母对应不同密字或不同原字母对应相同密字或者原信息中没有出现全部 26 个大写字母则破译失败输出Failed。否则用该映射的逆密字 → 原字母翻译第三行给出的加密信息并输出原文。解题步骤读入三行字符串s1密文、s2原文、s3待翻译密文。建立两个数组a[26]和b[26]分别表示原字母对应的密字和密字对应的原字母初始化为 -1未设置。遍历s1和s2的每个对应位置取原字母x s2[i] - A密字母y s1[i] - A。如果a[x]已设置且不等于y或b[y]已设置且不等于x则出现冲突直接输出Failed并结束。否则设置a[x] yb[y] x。检查是否 26 个原字母都出现过遍历x从 0 到 25若a[x] -1则输出Failed并结束。翻译s3对每个字符c取b[c - A]并转回大写字母输出。注意映射必须是双射且所有原字母必须出现否则失败。代码实现#includebits/stdc.husingnamespacestd;intmain(){string s1,s2,s3;cins1s2s3;// 读入三行inta[26],b[26];// a:原-密, b:密-原memset(a,-1,sizeof(a));// 初始化为-1memset(b,-1,sizeof(b));intns1.size();for(inti0;in;i){intxs2[i]-A;// 原字母编号intys1[i]-A;// 密文字母编号if(a[x]!-1a[x]!y){// 原字母已有不同密字coutFailedendl;return0;}if(b[y]!-1b[y]!x){// 密字已有不同原字母coutFailedendl;return0;}a[x]y;// 建立映射b[y]x;}for(inti0;i26;i){if(a[i]-1){// 原字母未出现coutFailedendl;return0;}}for(charc:s3){intyc-A;// 待翻译密文字母coutchar(b[y]A);// 输出对应的原字母}coutendl;return0;}功能分析输入处理使用cin依次读取三个由大写字母组成的字符串长度在 1~100 之间。映射建立用两个整型数组分别记录原字母 → 密字 和 密字 → 原字母 的对应关系同时检查是否违反双射规则包括同一原字母对应不同密字以及不同原字母对应同一密字。完整性检查确认所有 26 个原字母都至少出现过一次否则破译失败。翻译输出利用建立的逆映射b[]将第三行密文逐个翻译回原文并输出。【完整系列请查看专栏】信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}