雖然這看起來像Crypt Kicker Problem重複，事實並非如此。Crypt Kicker的更好解決方案？
我已經解決了這個問題，但我不都在一起滿意我的解決方案。這個問題的說法是：
加密文本的共同但有不安全的方法是置換的英文字母。換句話說，字母表中的每個字母在文本中都被其他字母替換。爲確保加密是可逆的，兩個字母不會被同一個字母替換。
你的任務是解密文本的多個編碼行，假設每個行使用不同的一組替代的，並且在解密文的所有單詞都從已知字的字典。
輸入
輸入由含有一個整數n的線，後跟n小寫字，每行一個，按字母順序排列的。這n個單詞組成可能出現在解密文本中的單詞字典。字典後面有幾行輸入。每行都按上面所述加密。
有沒有在字典中超過1000個字。沒有單詞超過16個字母。加密的行只包含小寫字母和空格，長度不超過80個字符。
輸出
解密每個行並打印到標準輸出。如果有多種解決方案，任何人都會這樣做。如果沒有解決方案，請用星號替換字母表中的每個字母。
採樣輸入
和
迪克
簡
粉撲
點
yertle
bjvg XSB hxsn XSB qymm XSB rqat XSB pnetfn
XXXX YYY ZZZZ WWW YYYY AAA BBBB CCC DDDDDD
樣本輸出
迪克和簡併抽吸和點和yertle
**** *** **** *** **** *** **** *** ******
我蠻橫逼迫了這個問題：我把字典分成了一個基於長度的集合。然後，我做了一個遞歸蠻力，我試着根據單詞長度嘗試每一個可能的替換，如果沒有匹配，就回溯。它可行，但我對解決方案非常不滿意。我可能只是在迷戀，但似乎應該有一個更優雅的方式來解決這個問題。我的代碼如下：
#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
#include<string>
#include<map>
#include<set>
using namespace std;
bool Find(vector<set<string > > &dict,vector<string> &line, map<char,char> &dec,int spot){
//Check that the end of the line hasn't been reached
if(spot<line.size()){
//Get the size of the current word
int sSize=line[spot].size();
string cand;
cand.resize(sSize,'A');
//Attempt to decode the current word
for(int i=0;i<sSize;i++){
if(dec.find(line[spot][i])!=dec.end())
cand[i]=dec[line[spot][i]];
}
//Check all strings in the dictionary of the current length
for(set<string>::iterator it=dict[sSize].begin();it!=dict[sSize].end();it++){
bool notMatch=false;
for(int i=0;i<sSize;i++)
//A is used to signify an undecoded character, this if says if the character was
// decoded and it does not equal to corresponding character in the word, it's not a match
if(cand[i]!='A'&&cand[i]!=(*it)[i])
notMatch=true;
if(notMatch)
continue;
for(int i=0;i<sSize;i++)
//if it is a feasible match, then add the learned characters to the decoder
if(cand[i]=='A')
dec.insert(pair<char,char> (line[spot][i],(*it)[i]));
//Keep decoding
if(Find(dict,line,dec,spot+1))
return true;
//If decoding failed, then remove added characters
for(int i=0;i<sSize;i++)
if(cand[i]=='A')
dec.erase(line[spot][i]);
}
if(spot==0){
//This means no solution was found, fill decoder with a map to astericks
string b="qwertyuiopasdfghjklzxcvbnm";
for(int i=0;i<b.size();i++)
dec.insert(pair<char,char> (b[i],'*'));
}
return false;
}
return true;
}
int main(){
int size;
cin >> size;
vector<set<string> > dict;
dict.resize(17);
string grab;
for(int i=0;i<size;i++){
//Bucket dictionary
cin >> grab;
dict[grab.size()].insert(grab);
}
while(getline(cin,grab)){
stringstream in(stringstream::in |stringstream::out);
in << grab;
vector<string> line;
while(in >> grab)
line.push_back(grab);
map<char,char> dec;
Find(dict,line,dec,0);
for(int i=0;i<line.size();i++){
for(int j=0;j<line[i].size();j++)
cout << dec[line[i][j]];
if(i!=line.size()-1)
cout << " ";
else
cout << endl;
}
}
}
另外，我不是特別感興趣的解決方案，不會在c + +工作。僅僅因爲這是我在編程比賽中使用的語言，所以我只能用它來解決這些問題。我也知道，有不少風格和次要效率的東西，我可以採取不同的做法，而不是太在乎我，我錯過了一兩次休息。主要我只是想知道是否有更簡單的解決方案，或者如果我的實現過於複雜的事情。謝謝。
招呼雅各，你讓你的解決方案接受？我測試了你的，並沒有爲我的輸入工作。 – Clash 2011-04-18 17:58:43