Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
You have been contracted by a terrorist group to crack encrypted transmissions. The only information that the terrorists could give you regarding the encrypted message is that a fixed key-length XOR-encryption algorithm was used to encode it. After a brief search on the 'Net, you find the following definition of XOR-encryption:
Assuming that we have a character u[i] from the unencrypted input stream, and a key k of length l with characters k[j], 0 <= j < l, then the encrypted value e[i] is obtained as follows:
e[i] = u[i] XOR k[i MOD l]
where MOD is the remainder after integer division (the % operator in C, C++ and Java), and XOR is the bitwise XOR operator applied to an 8-bit character (the ^ operator in C, C++ and Java). XOR encryption is a symmetric encryption scheme, so that the message is decoded by encrypting the encrypted message (a second time) with the same key, so that
u[i] = e[i] XOR k[i MOD l]
You are given four encrypted input streams of 30 000 characters each (that is, a continuous input stream of 120 000 characters). Your program must output the four decrypted stream with no other characters embedded. The streams were encrypted using XOR encryption with fixed length keys of fewer than 30 characters. Each character in the key is unique (appears only once), and is selected from the set a..z merged with 0..9.
Your task is to determine the correct key length, and decrypt the encrypted input stream.
Your terrorist friends provided you with one last vital piece of information: ��The decrypted message will be in English.'��
It is recommended that you write an XOR encryption program first to aid you in testing your solution.