题目描述给定一段已知的自然语言文本KNOWN\texttt{KNOWN}KNOWN和一段经过单字母替换加密的文本ENCODED\texttt{ENCODED}ENCODED。加密映射是字母表到自身的双射。假设同一作者在不同文本中使用字母的相对频率相同。程序需统计KNOWN\texttt{KNOWN}KNOWN和ENCODED\texttt{ENCODED}ENCODED中各字母的出现次数不区分大小写但仅统计字母分别按频率降序排列频率相同则按字母升序。然后将KNOWN\texttt{KNOWN}KNOWN中最常见的字母对应到ENCODED\texttt{ENCODED}ENCODED中最常见的字母次常见对应次常见依此类推得到解密映射。最后用该映射解码ENCODED\texttt{ENCODED}ENCODED输出时保留大小写非字母字符原样输出。输入格式输入包含两个段落由空行分隔。第一段为KNOWN\texttt{KNOWN}KNOWN第二段为ENCODED\texttt{ENCODED}ENCODED。每段可包含多行可能包含空行。输入以文件结束终止。输出格式输出解码后的完整消息与ENCODED\texttt{ENCODED}ENCODED的格式一致包括空行和非字母字符。样例输入The car is blue. Wkh fdu 1v eoxh.样例输出The car is blue.题目分析该题要求利用统计频率推断替换密码的映射。由于加密为单表替换且双射频率分析是经典方法。已知文本与加密文本来自同一作者因此字母频率分布相似最高频字母对应最高频字母依此类推。虽然实际中频率可能不完全严格对应但题目约定按此规则推断。需要处理大小写不敏感统计但大小写敏感输出非字母字符保留。解题思路实现步骤确定如下步骤1\texttt{1}1. 读取KNOWN\texttt{KNOWN}KNOWN的所有行直到遇到空行。统计每个字母转换为小写的出现次数存入映射known\textit{known}known。步骤2\texttt{2}2. 读取ENCODED\texttt{ENCODED}ENCODED的所有行直到文件结束将每行追加到字符串message\textit{message}message中并保留换行符。同时统计每个字母小写的出现次数存入映射unknown\textit{unknown}unknown。步骤3\texttt{3}3. 将known\textit{known}known和unknown\textit{unknown}unknown分别转换为结构体数组按频率降序、字母升序排序。步骤4\texttt{4}4. 建立映射表mapping\textit{mapping}mapping对于排序后的第iii个位置将加密文本中第iii个字母映射到已知文本中第iii个字母。步骤5\texttt{5}5. 遍历message\textit{message}message的每个字符若为字母则取其小写形式查找映射再根据原字符大小写还原若非字母则原样输出。该算法复杂度为O((L1L2)26log⁡26)O((L_1 L_2) 26 \log 26)O((L1​L2​)26log26)其中L1L_1L1​和L2L_2L2​分别为两段文本的长度极为高效。代码实现// Decode// UVa ID: 726// Verdict: Accepted// Submission Date: 2018-03-21// UVa Run Time: 0.070s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structfrequency{charletter;intcnt;frequency(charletter0,intcnt0):letter(letter),cnt(cnt){}booloperator(constfrequencyf)const{if(cnt!f.cnt)returncntf.cnt;returnletterf.letter;}};intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string line;mapchar,intknown,unknown;while(getline(cin,line),line.length()0){for(autoc:line)if(isalpha(c))known[tolower(c)];}string message;while(getline(cin,line)){messageline;message\n;for(autoc:line)if(isalpha(c))unknown[tolower(c)];}vectorfrequencyf1,f2;for(autop:known)f1.push_back(frequency(p.first,p.second));for(autop:unknown)f2.push_back(frequency(p.first,p.second));sort(f1.begin(),f1.end());sort(f2.begin(),f2.end());mapchar,charmapping;for(inti0;if1.size();i)mapping[f2[i].letter]f1[i].letter;for(autoc:message)if(isalpha(c)){charmappedmapping[tolower(c)];if(isupper(c))mappedtoupper(mapped);coutmapped;}elsecoutc;return0;}总结本题利用频率分析破解单表替换密码基于已知文本与加密文本的频率排序一致性。关键点在于正确处理大小写、非字母字符和空行。统计时使用小写统一输出时还原大小写。排序时频率相同按字母升序保证映射唯一。算法简单高效是频率分析法的典型应用。