题目描述题目要求根据加密后的密码和一篇论文文本还原出原始密码。密码由两个单词和一个数字组合而成格式为word1 digit word2或word2 digit word1其中两个单词均来自论文文本中的单词仅由字母组成长度至少为222不区分大小写。数字只能是000、222、444或888。密码总长度在555到888个字符之间。密码中所有字母均为小写。加密函数crypt()\texttt{crypt()}crypt()使用给定的222字符盐值salt\textit{salt}salt对密码进行加密加密结果的前两个字符即为salt\textit{salt}salt本身。输入格式第一行一个字符串表示加密后的密码。接下来若干行每行不超过808080个可打印ASCII\texttt{ASCII}ASCII字符表示论文正文。论文正文中单词定义为连续的字母字符大写或小写由空格或标点分隔。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式输出一行即还原出的原始密码。样例输入h8E6dqt5lkL9o The parallel algorithms were executed on the Connection Machine model CM-2 --- a single-instruction multiple data (SIMD) parallel computer which, in its largest configuration, contains 65,536 bit-serial processors and 2048 Weitek floating-point units (FPUs). The bit-serial processors are clustered together into groups of 16 within a single integrated circuit, and these ICs are connected together in a 12-dimensional hypercube. Two ICs, or 32 processors, share a single Weitek FPU. Note that a fully configured CM-2 contains 2048 times as much floating point hardware as a conventional computer containing a single Weitek FPU (e.g., a SUN-4).输出bit0note题目分析本题的核心是从论文文本中提取所有可能的单词枚举所有可能的单词对和数字组合使用crypt()\texttt{crypt()}crypt()函数加密后与给定的加密密码比对找到匹配的原始密码。单词提取从论文文本中提取所有长度至少为222的连续字母序列并转换为小写存储。注意单词不区分大小写因为原始密码中的字母均为小写。密码候选生成设提取到的单词集合为WWW。对于WWW中的任意两个单词wiw_iwi​和wjw_jwj​i≠ji \ne jij以及数字d∈{0,2,4,8}d \in \{0, 2, 4, 8\}d∈{0,2,4,8}生成候选密码widwjw_i d w_jwi​dwj​wjdwiw_j d w_iwj​dwi​要求候选密码的长度在555到888之间含两端。加密与比对加密函数crypt()\texttt{crypt()}crypt()需要两个参数待加密的密码key\textit{key}key和盐值salt\textit{salt}salt。盐值可以从给定的加密密码中提取即加密密码的前两个字符。然后对每个候选密码调用crypt(key, salt)\texttt{crypt(key, salt)}crypt(key, salt)将返回的加密字符串与输入加密密码进行比对。若匹配则输出该候选密码。实现注意事项需要包含头文件crypt.h并链接加密库通常为-lcrypt。crypt()\texttt{crypt()}crypt()函数返回的静态数据在每次调用时会被覆盖因此应在比对前保存加密密码或立即进行比较。单词集合可能较大但论文文本长度有限每行不超过808080字符总行数不定枚举所有单词对的时间复杂度为O(M2)O(M^2)O(M2)其中MMM为不同单词的数量。实际输入中MMM不会太大可在可接受范围内运行。复杂度分析设不同单词数量为MMM则最多检查O(M2×4)O(M^2 \times 4)O(M2×4)个候选密码每次调用crypt()\texttt{crypt()}crypt()耗时较小MMM通常不超过几百完全可接受。代码实现// Enigmatic Encryption// UVa ID: 425// Verdict: Accepted// Submission Date: 2016-07-20// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.h#includecrypt.h//#include unistd.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);string passwordline;string saltline.substr(0,2);setstringwords;while(getline(cin,line)){inti0;while(iline.length()){if(isalpha(line[i])){string block;while(iline.length()isalpha(line[i])){blocktolower(line[i]);i;}if(block.length()1)words.insert(block);}elsei;}}vectorstringallWords;for(autoword:words)allWords.push_back(word);chardigits[4]{0,2,4,8};for(inti0;iallWords.size();i)for(intji1;jallWords.size();j){if(ij)continue;intlengthallWords[i].length()allWords[j].length();if(length4length7){for(intk0;k4;k){string plain1allWords[i]digits[k]allWords[j];char*encryptedcrypt(plain1.data(),salt.data());if(strcmp(encrypted,password.data())0){coutplain1\n;return0;}string plain2allWords[j]digits[k]allWords[i];encryptedcrypt(plain2.data(),salt.data());if(strcmp(encrypted,password.data())0){coutplain2\n;return0;}}}}return0;}