Crypt Kicker

A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter.

Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of replacements, and that all words in the decrypted text are from a dictionary of known words.

Input 

The input consists of a line containing an integer n, followed by n lower case words, one per line, in alphabetical order. These n words comprise the dictionary of words which may appear in the decrypted text. Following the dictionary are several lines of input. Each line is encrypted as described above.

There are no more than 1000 words in the dictionary. No word exceeds 16 letters. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length.

Output 

Decrypt each line and print it to standard output. If there is more than one solution, any will do. If there is no solution, replace every letter of the alphabet by an asterisk.

Sample 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

Sample Output 

dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

---

Miguel Revilla 2002-06-15

題目要求字母一對一對應，然後根據加密文件，每個單字解出來都必須在字典中。

答案有很多的話，則只輸出一種。

不可能窮舉字母對應方式 O(26!)，當遇到單字無法依照當前對應方式進行解密，
則試圖在字典中找一單字與其對應，並將新的字母對應放入表格中。反之，
如果能全部找到對應方式，則去在字典中查找是否有其單字。

持續到所有單字都被解密。


#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
string word[1005];
set<string> W;
string buf[1005];
int n, m;
bool hasSol;
char mapped[128], mapped2[128];
char trans[128];
void dfs(int idx) {//decode buf[idx]
    if(hasSol)  return;
    int i, j, err;
    int exist = 1;
    if(idx == m) {
        for(i = 0; i < m; i++) {
            if(i)   putchar(' ');
            for(j = 0; j < buf[i].length(); j++)
                putchar(mapped[buf[i][j]]);
        }
        puts("");
        hasSol = 1;
        return;
    }
    for(i = 0; i < buf[idx].length(); i++) {
        if(mapped[buf[idx][i]] == 0)
            exist = 0;
        else {
            trans[i] = mapped[buf[idx][i]];
        }
    }
    trans[i] = '\0';
    if(exist == 1) {
        if(W.find(trans) == W.end())
            return;
        dfs(idx+1);
    } else {//try new mapped function
        char ori[128], ori2[128];
        for(i = 0; i < n; i++) {
            if(buf[idx].length() != word[i].length())
                continue;
            memcpy(ori, mapped, sizeof(ori));//copy
            memcpy(ori2, mapped2, sizeof(ori2));//copy
            err = 0;
            for(j = 0; j < word[i].length(); j++) {
                if(mapped[buf[idx][j]] == 0) {
                    if(mapped2[word[i][j]])
                        err = 1;
                    mapped[buf[idx][j]] = word[i][j];
                    mapped2[word[i][j]] = buf[idx][j];
                    // new function
                } else {
                    if(mapped[buf[idx][j]] != word[i][j]) {
                        err = 1;
                        break;
                    }
                }
            }
            if(err == 0)
                dfs(idx+1);
            memcpy(mapped, ori, sizeof(ori));//recover
            memcpy(mapped2, ori2, sizeof(ori2));//recover
            if(hasSol)
                return;
        }
    }
}
int main() {
    scanf("%d", &n);
    int i, j;
    string line;
    char s[128];
    for(i = 0; i < n; i++) {
        scanf("%s", s);
        word[i] = s;
        W.insert(s);
    }
    while(getchar() != '\n');
    while(getline(cin, line)) {
        stringstream sin(line);
        m = 0;
        while(sin >> line)
            buf[m++] = line;
        memset(mapped, 0, sizeof(mapped));
        memset(mapped2, 0, sizeof(mapped2));
        hasSol = false;
        dfs(0);
        if(!hasSol) {
            for(i = 0; i < m; i++) {
                if(i)   putchar(' ');
                for(j = buf[i].length()-1; j >= 0; j--)
                    putchar('*');
            }
            puts("");
        }
    }
    return 0;
}