Caesar Cypher

One of the earliest encrypting systems is attributed to Julius Caesar: if the letter to be encrypted is the Nth letter in the alphabet, replace it with the (N+K)th where K is some fixed integer (Caesar used K = 3). We usually treat a space as zero and all arithemtic is then done modulo 27. Thus for K = 1 the message `ATTACK AT DAWN' becomes `BUUBDLABUAEBXO'.

Decrypting such a message is trivial since one only needs to try 26 different values of K. This process is aided by knowledge of the language, since then one can determine when the decrypted text forms recognisable words. If one does not know the language, then a dictionary would be necessary.

Write a program that will read in a dictionary and some encrypted text, determine the value of K that was used, and then decrypt the cyphertext to produce the original message. The original message contained only letters and spaces and has been encrypted using the above method. The most suitable value of K will be the one which produces the most matches with the words in the dictionary.

Input 

Input will consist of a dictionary and the encrypted text. The dictionary will consist of no more than 100 lines each containing a word in uppercase characters and not more than 20 characters in length. The dictionary portion will be terminated by a line consisting of a single `#'. The encrypted text will follow immediately and will consist of a single line containing no more than 250 characters. Note that the dictionary will not necessarily contain all the words in the original text, although it will certainly contain a large portion of them. It may also contain words that are not in the original text. The dictionary will not appear in any particular order.

Output 

Output will consist of the decrypted text. Lines should be as long as possible, but not exceeding 60 characters and no word may cross a linebreak.

Sample Input 

THIS
DAWN
THAT
THE
ZORRO
OTHER
AT
THING
#
BUUBDLA PSSPABUAEBXO

Sample Output 

ATTACK ZORRO AT DAWN

---

Miguel A. Revilla
1998-03-10

一行最多印 60 個字元，不允許一個單字跨過一行。
這一點比較不容易處理！

#include <stdio.h>
#include <string.h>
#include <map>
#include <iostream>
#include <sstream>
using namespace std;
int main() {
    char s[1024], d[1024];
    map<string, int> R;
    while(gets(s)) {
        if(!strcmp(s, "#"))
            break;
        R[s] = 0;
    }
    gets(s);
    int i, j, k, len = strlen(s);
    string res;
    int mxcnt = -1;
    for(i = 1; i < 27; i++) {
        for(j = 0; j < len; j++) {
            if(s[j] == ' ') k = 0;
            else            k = s[j]-'A'+1;
            k = (k-i+27)%27;
            if(k == 0)  d[j] = ' ';
            else        d[j] = k+'A'-1;
        }
        d[len] = '\0';
        stringstream sin(d);
        string token;
        int cnt = 0;
        while(sin >> token) {
            map<string, int>::iterator it = R.find(token);
            if(it != R.end())
                cnt++;
        }
        if(cnt > mxcnt)
            res = d, mxcnt = cnt;
    }
    stringstream sin(res);
    string token;
    int col = 0;
    int first = 0;
    while(sin >> token) {
        if(col + token.length() >= 60)
            cout << endl, col = 0, first = 0;
        if(first)   putchar(' ');
        first = 1;
        col += first + token.length();
        cout << token;
    }
    cout << endl;
    return 0;
}