| 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 nescessary.
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 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 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.
THIS DAWN THAT THE ZORRO OTHER AT THING # BUUBDLA PSSPABUAEBXO
ATTACK ZORRO AT DAWN