Consider a simple encryption algorithm based on the move-to-front heuristic.
Both the unencrypted (plaintext) and encrypted (ciphertext) messages are Strings
composed of uppercase letters ('A'-'Z') and spaces (' '). The encryption algorithm
maintains a state which is a permutation of the 27 possible characters. The key used
to encrypt and decrypt messages is the initial permutation.
Encryption processes the plaintext from left to right, outputting one character of
the ciphertext for each character of the plaintext. At each position of the plaintext,
the encryption algorithm performs the following steps:
- Find the (zero-based) position of the plaintext character in the current permutation.
- If the position is 0-25, output 'A'-'Z', respectively. If the position is 26, output a space.
- Move the plaintext character to the front of the permutation (ie, delete it from its
current position in the permutation and re-insert it at the front).
For example, starting with a key "ZYXWVUTSRQPON MLKJIHGFEDCBA" and a plaintext
"TPCDR" (all quotes for clarity only), encryption would proceed as follows:
- State = "ZYXWVUTSRQPON MLKJIHGFEDCBA". 'T' is in position 6, output 'G'.
- State = "TZYXWVUSRQPON MLKJIHGFEDCBA". 'P' is in position 10, output 'K'.
- State = "PTZYXWVUSRQON MLKJIHGFEDCBA". 'C' is in position 24, output 'Y'.
- State = "CPTZYXWVUSRQON MLKJIHGFEDBA". 'D' is in position 24, output 'Y'.
- State = "DCPTZYXWVUSRQON MLKJIHGFEBA". 'R' is in position 11, output 'L'.
The final ciphertext is "GKYYL". (The final state is
"RDCPTZYXWVUSQON MLKJIHGFEBA", but that is discarded by the
algorithm.)
You will be given both the plaintexts and the ciphertexts of several messages, where the i-th ciphertext
is believed to be the encrypted form of the i-th plaintext, and all the messages are believed
to have been encrypted using the same key. Your task is to recover and return that key (as a String).
If the messages do not contain enough information to fully determine the key, the output
of your method should summarize the set of possible keys by
placing a '-' character at any position of the permutation that has not
been narrowed down to a single possible character. If no key exists that could have been used
to encrypt all the messages, output "ERROR".
Notice that, when encrypting multiple messages, the state is not carried over from one message to the next, but rather is re-initialized for each message.
|