UVa 179 Code Breaking

题目分析题目描述了一种简单的加密方法周期置换加密。给定一个周期kkk和一个长度为kkk的置换即111到kkk的一个排列将明文按kkk个字符一组进行分组最后一组不足时用?补齐然后对每组应用该置换得到密文。输入包含若干个三元组(plaintext, ciphertext1, ciphertext2)每行一个字符串以单独一行#结束。我们需要判断是否存在某个周期kkk和对应的置换使得plaintext加密后得到ciphertext1。如果存在选择最小的kkk题面保证此时置换唯一然后将ciphertext2按照逆置换解密并输出不足时补?。如果不存在这样的置换则直接输出ciphertext2原样。解题思路1. 候选周期kkk的筛选对于某个kkk若存在一个置换将plaintext映射到ciphertext1则对于每个长度为kkk的块最后一组可以不足块中字符的多重集必须相同。因为置换只是重新排列字符不改变字符集合。因此我们可以枚举所有可能的kkk从111到plaintext的长度对每个kkk将明文和密文按kkk分组比较每组的排序后结果是否一致。若所有组都一致则kkk是一个候选周期。2. 验证置换的存在并找出最小kkk对于候选周期kkk需要判断是否存在一个长度为kkk的置换将明文块映射到对应的密文块。由于kkk较小输入行长度不超过808080我们可以采用以下两种方法全排列枚举当k≤7k \le 7k≤7时k!k!k!较小可直接枚举所有排列进行验证。回溯DFS\texttt{DFS}DFS匹配当kkk较大时利用每个位置上的字符对应关系进行约束回溯。因为一个置换将明文的第iii个字符映射到密文的第p(i)p(i)p(i)个位置实际上等价于寻找一个双射满足plaintext[i] ciphertext1[p(i)]。我们可以从第一个块中提取这种对应关系然后递归构造置换。由于kkk从111到nnn递增进行尝试第一个成功的就是最小的kkk。3. 解密ciphertext2\texttt{ciphertext2}ciphertext2找到置换后存储在key数组中key[i]表示明文中第iii个字符在密文中的位置从111开始解密需要应用逆置换对于密文中的第jjj个位置它对应明文中的第pos[j]个位置。我们可以先求出逆置换inv然后按kkk分组对ciphertext2进行解密每组不足时用?补齐。代码实现// Code Breaking// UVa ID: 179// Verdict: Accepted// Submission Date: 2016-03-27// UVa Run Time: 0.026s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;string plaintext,cyphertext1,cyphertext2;vectorintk,key;// k存放所有候选周期key存放找到的置换1-indexed// 给定明文块用当前key加密返回密文块stringencrypt(string plain){stringencrypted(plain);for(inti0;i(int)key.size();i)encrypted[key[i]-1]plain[i];returnencrypted;}// 使用当前key对密文进行解密并输出每组不足补?voiddecrypt(string encrypted){intindex0;intkeyLengthkey.size();inttextLengthencrypted.length();while(indextextLength){intsubLengthmin(keyLength,textLength-index);string subEncryptedencrypted.substr(index,subLength);// 补全到keyLength长度便于置换while((int)subEncrypted.length()keyLength)subEncrypted?;// 应用逆置换key中存储的是正向映射此处直接按正向输出即可// 注意这里的key在解密时实际上是正向映射但因为我们加密时是encrypted[key[i]-1] plain[i]// 所以解密时应该取encrypted的第j个字符放到plain的第?位等价于正向映射本身。// 更准确地说如果key[i]表示plain[i]去了密文的key[i]位置则解密时密文位置key[i]-1的字符应回到i。// 这里的写法是直接按key索引输出实际上是正确的见题目样例验证。for(inti0;ikeyLength;i)coutsubEncrypted[key[i]-1];indexkeyLength;}}// 验证当前key是否能将plaintext映射为cyphertext1boolverifyKey(){intindex0;intkeyLengthkey.size();inttextLengthplaintext.length();while(indextextLength){intsubLengthmin(keyLength,textLength-index);string subPlainplaintext.substr(index,subLength);string subEncryptedcyphertext1.substr(index,subLength);// 补全到keyLength长度while((int)subPlain.length()keyLength)subPlain?;while((int)subEncrypted.length()keyLength)subEncrypted?;if(encrypt(subPlain)!subEncrypted)returnfalse;indexkeyLength;}returntrue;}// 初始化key为[1,2,...,keyLength]voidinitializeKey(intkeyLength){key.clear();for(inti1;ikeyLength;i)key.push_back(i);}// 小k时直接全排列验证boolfindPermutation(intkeyLength){initializeKey(keyLength);do{if(verifyKey())returntrue;}while(next_permutation(key.begin(),key.end()));returnfalse;}// ---------- 回溯法找置换大k时用 ----------intmaxTimesTry10000;// 避免极端情况inttimesTried0;boolkeyFoundfalse,finishfalse;string source,target;// 当前块的明文和密文vectorboolmatched;// 标记密文字符是否已被分配voidbacktrack(intindex,intkeyLength){if(indexkeyLength){if(verifyKey()){keyFoundtrue;finishtrue;}if(timesTriedmaxTimesTry)finishtrue;return;}// 明文第index个字符必须匹配密文的某个未被占用的位置的字符for(inti0;i(int)target.length();i){if(!matched[i]source[index]target[i]){matched[i]true;key[index]i1;// 置换值从1开始backtrack(index1,keyLength);if(finish)return;matched[i]false;}}}// 利用第一个完整的块进行回溯匹配boolfindKeyByBacktrack(intkeyLength){// 找到第一个完整的块长度等于keyLengthintindex0;while(index(int)plaintext.length()){initializeKey(keyLength);finishfalse;timesTried0;keyFoundfalse;sourceplaintext.substr(index,keyLength);targetcyphertext1.substr(index,keyLength);if((int)source.length()keyLength)break;// 最后一个不完整块不作为依据matched.assign(keyLength,false);backtrack(0,keyLength);if(keyFound)break;indexkeyLength;}returnkeyFound;}// 在候选周期k中寻找可行置换boolfindKey(){for(inti0;i(int)k.size();i){// 小k直接全排列if(k[i]7findPermutation(k[i]))returntrue;// 大k回溯if(findKeyByBacktrack(k[i]))returntrue;}returnfalse;}// 筛选候选周期k通过字符多重集比较boolfindK(){k.clear();intkeyLength1;inttextLengthplaintext.length();while(keyLengthtextLength){intindex0;boolkeyLengthMatchedtrue;while(indextextLength){intsubLengthmin(keyLength,textLength-index);string subText1plaintext.substr(index,subLength);string subText2cyphertext1.substr(index,subLength);sort(subText1.begin(),subText1.end());sort(subText2.begin(),subText2.end());if(subText1!subText2){keyLengthMatchedfalse;break;}indexkeyLength;}if(keyLengthMatched)k.push_back(keyLength);keyLength;}return!k.empty();}intmain(){cin.tie(0);cout.sync_with_stdio(false);while(getline(cin,plaintext),plaintext!#){getline(cin,cyphertext1);getline(cin,cyphertext2);if(findK()findKey())decrypt(cyphertext2);elsecoutcyphertext2;cout\n;}return0;}算法复杂度筛选候选kkkO(n2log⁡n)O(n^2 \log n)O(n2logn)nnn为字符串长度。置换查找小kkk时O(k!⋅n)O(k! \cdot n)O(k!⋅n)大kkk时通过回溯剪枝实际效率很高。整体可在输入规模下高效运行。总结本题的核心在于两点利用字符多重集快速筛选可能的周期kkk避免无效枚举。对于给定的kkk通过置换匹配小范围枚举或回溯确定具体的映射关系并选择最小的可行kkk。解密时注意应用逆置换并正确处理末尾补?的情况。