Хотя это похоже на дубликат Crypt Kicker Problem , это не так.
Я решил проблему, но не все вместе удовлетворены моим решением. Постановка проблемы:
Распространенным, но небезопасным методом шифрования текста является перестановка букв алфавита. Другими словами, каждая буква алфавита последовательно заменяется в тексте другой буквой. Чтобы гарантировать, что шифрование обратимо, никакие две буквы не заменяются одной и той же буквой.
Ваша задача - расшифровать несколько закодированных строк текста, предполагая, что каждая строка использует различный набор замен, и что все слова в расшифрованном тексте взяты из словаря известных слов.
Ввод
Входные данные состоят из строки, содержащей целое число n, за которым следуют n строчных слов, по одному на строку, в алфавитном порядке. Эти n слов составляют словарь слов, которые могут появиться в расшифрованном тексте. За словарем следуют несколько строк ввода. Каждая строка зашифрована, как описано выше.
В словаре не более 1000 слов. Ни одно слово не превышает 16 букв. Зашифрованные строки содержат только строчные буквы и пробелы и не превышают 80 символов в длину.
выход
Расшифровывать каждую строку и выводить ее на стандартный вывод. Если есть несколько решений, подойдет любое. Если решения не существует, замените каждую букву алфавита звездочкой.
Пример ввода
6
и
член
Джейн
слоеный
пятно
yertle
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx гггг zzzz www гггг ааа 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 ++. Просто потому, что это язык, с которым я работаю в конкурсе по программированию, поэтому я ограничен им для решения этих проблем. Я также знаю, что есть довольно много стилистических и незначительных вещей, которые я мог бы сделать по-другому, которые меня не слишком волнуют, я пропускаю один или два перерыва. В основном мне просто интересно, есть ли более простое решение, или моя реализация слишком усложняет вещи. Спасибо.