Теперь я пытаюсь решить проблему UVa 843: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=784
И вот код на C ++, который я пробовал для этого.
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
void decode(int start, std::string& match);
bool canMatch(std::string& match, std::string w, std::string d);
bool hasConflict(std::string match);
int N;
std::vector<std::string> dict; // Dictionary for allowed words
std::vector<std::string> words; // List of words that is in a line for decrypting
std::set<std::string> exist; // Set of `dict` for faster searching
std::set<std::string>::iterator it; // Iterator for the set
std::string temp; // Temp buffer for string
std::string cyphertext; // Input line (encrypted)
bool done = false; // Flag for done decrypting
int main(){
// Building dictionary, set used to find word faster
std::cin >> N;
for(int i = 0;i < N;++i){
std::cin >> temp;
if((it = exist.find(temp)) == exist.end()){
dict.push_back(temp);
exist.insert(temp);
}
}
// Decrept each line
scanf("%*c");
while(getline(std::cin, cyphertext)){
// For empty lines
if(!cyphertext.length()){
continue;
}
// Initialize
std::string match(26, '*');
done = false;
// Parse the words in line into vector.
words.clear();
std::istringstream iss(cyphertext);
while(iss >> temp){
words.push_back(temp);
}
decode(0, match);
// Debug
// std::cout << "Result: ============================\n";
// std::cout << "The matching is:\n";
// std::cout << "abcdefghijklmnopqrstuvwxyz\n";
// std::cout << match << "\n";
// Restore
//std::cout << cyphertext << "\n";
if(!done){
match.assign(26, '*');
}
temp = "";
for(int i = 0;i < cyphertext.length();++i){
if(cyphertext[i] == ' '){
temp += ' ';
}
else{
temp += match[cyphertext[i] - 'a'];
}
}
std::cout << temp << "\n";
}
return 0;
}
// Backtracking for decoding
void decode(int start, std::string& match){
// Search from the first word
std::string backupCypher = match;
for(int i = 0;i < dict.size();++i){
// std::cout << "Trying to decode word \"" << words[start] << "\"\n";
match = backupCypher;
if(dict[i].length() == words[start].length()){
if(canMatch(match, words[start], dict[i])){
if(start == words.size() - 1){
// std::cout << "End of sentence reached.\n";
// std::cout << "Current match:\n";
// std::cout << "abcdefghijklmnopqrstuvwxyz\n";
// std::cout << match << "\n\n\n";
done = true;
}
else{
// std::cout << "Advancing to next word.\n";
// std::cout << "Current match:\n";
// std::cout << "abcdefghijklmnopqrstuvwxyz\n";
// std::cout << match << "\n\n\n";
decode(start + 1, match);
if(done){
break;
}
match = backupCypher;
}
}
}
// Check if is done
if(done){
break;
}
}
return;
}
// Try matching the word d with the encrypted word w
bool canMatch(std::string& match, std::string w, std::string d){
for(int i = 0;i < w.length();++i){
if(match[w[i] - 'a'] == '*' || match[w[i] - 'a'] == d[i]){
match[w[i] - 'a'] = d[i];
}
else{
// std::cout << "Matching " << w[i] << " to " << d[i] << " Failed!\n";
return false;
}
}
if(hasConflict(match)){
// std::cout << "Has conflict!\n";
// std::cout << "abcdefghijklmnopqrstuvwxyz\n";
// std::cout << match << "\n";
return false;
}
return true;
}
bool hasConflict(std::string match){
bool used[26] = {false};
std::sort(match.begin(), match.end());
for(auto iter = match.begin();iter != match.end();++iter){
if(used[*iter - 'a']){
return true;
}
used[*iter - 'a'] = true;
}
return false;
}
который получает неправильные ответы. Прочитав статью Как отлаживать мой код , я попробовал различные входы suDebug и самописные входы, распечатал значения переменных с рекомендованными std::cout s, а также построил следующий генератор случайных входов с тестированием на сайте uDebug, который всегда сообщает мне, что все мои результаты верны. Интересно, есть ли другие методы для отладки Когда я не могу найти случай ввода, который вызывает ошибку ?
Кстати, это генератор ввода, который я написал:
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>
int main(){
char carr[] = {'a', 'b', 'c', 'd', 'e',
'f', 'g', 'h', 'i', 'j',
'k', 'l', 'm', 'n', 'o',
'p', 'q', 'r', 's', 't',
'u', 'v', 'w', 'x', 'y', 'z'};
int randNum;
srand(time(NULL));
std::cout << (randNum = rand() % 1000 + 1) << "\n";
for(int i = 0;i < randNum;++i){
int len = rand() % 16 + 1;
std::string temp = "";
for(int j = 0;j < len;++j){
temp += carr[rand() % 26];
}
std::cout << temp << "\n";
}
for(int i = 0;i < 100;++i){
std::string temp = "";
int count = 0;
do{
++count;
int len = rand() % 16 + 1;
for(int j = 0;j < len;++j){
temp += carr[rand() % 26];
}
temp += " ";
}while(rand() % 3 != 0 && count < 10);
temp.pop_back();
std::cout << temp << std::endl;
}
return 0;
}
Большое спасибо за помощь.
Некоторые входные и выходные данные: (Первый задан проблемой, второй написан самим собой.)
Input:
6
and
dick
jane
puff
spot
yertle
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd
Output:
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******
Input:
3
a
aa
aaa
z
zz
zzz
xx
cc
zzz xx c
zzz zz z
zzz xx zz z
(Empty Line)
xx
Output:
a
aa
aaa
aa
aa
*** ** *
aaa aa a
*** ** ** *
aa