企业官网建设流程全解析

题目描述

题目要求根据加密后的密码和一篇论文文本，还原出原始密码。密码由两个单词和一个数字组合而成，格式为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 (FPU's). The bit-serial processors are clustered together into groups of 16 within a single integrated circuit, and these IC's are connected together in a 12-dimensional hypercube. Two IC's, 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}，生成候选密码：

• wi+d+wjw_i + d + w_jwi​+d+wj​
• wj+d+wiw_j + d + w_iwj​+d+wi​

要求候选密码的长度在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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>#include<crypt.h>//#include <unistd.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);string password=line;string salt=line.substr(0,2);set<string>words;while(getline(cin,line)){inti=0;while(i<line.length()){if(isalpha(line[i])){string block;while(i<line.length()&&isalpha(line[i])){block+=tolower(line[i]);i++;}if(block.length()>1)words.insert(block);}elsei++;}}vector<string>allWords;for(autoword:words)allWords.push_back(word);chardigits[4]={'0','2','4','8'};for(inti=0;i<allWords.size();i++)for(intj=i+1;j<allWords.size();j++){if(i==j)continue;intlength=allWords[i].length()+allWords[j].length();if(length>=4&&length<=7){for(intk=0;k<4;k++){string plain1=allWords[i]+digits[k]+allWords[j];char*encrypted=crypt(plain1.data(),salt.data());if(strcmp(encrypted,password.data())==0){cout<<plain1<<'\n';return0;}string plain2=allWords[j]+digits[k]+allWords[i];encrypted=crypt(plain2.data(),salt.data());if(strcmp(encrypted,password.data())==0){cout<<plain2<<'\n';return0;}}}}return0;}