虽然这看起来像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