Problem C
Chasing Subs
From previous intelligence operations (the details of which we are not at liberty to reveal to you), it is known that the messages are likely encrypted with a simple substitution cipher. In other words, every letter is replaced with another letter from the alphabet (a letter could also remain unchanged). So for instance, it could be that every ‘a’ gets turned into a ‘k’, every ‘b’ remains a ‘b’, every ‘c’ becomes an ‘a’, and so on. Obviously, different letters in the original message become different letters in the encrypted one, otherwise decryption would not be unique.
Alas it is not known which letters are substituted for which other letters. However, a suspicious person in scuba gear has been apprehended and was found carrying a note with what appears to be a fragment of a decrypted message. If this fragment could be matched to an encrypted message, the code can be broken!
Can you help MUST find out if the message fragment could be part of a given encrypted message, and if so, in how many positions?
Input
The input consists of:
-
one line with a string consisting of at least $1$ and at most $250\, 000$ lowercase letters, the encrypted message;
-
one line with a string consisting of at least $1$ and at most $250\, 000$ lowercase letters, the decrypted fragment.
Output
If there is a unique position in the encrypted message where the message fragment could occur, output the substring of the encrypted message that could correspond to the fragment. Otherwise, output the number of positions in the encrypted message where the fragment could occur.
| Sample Input 1 | Sample Output 1 |
|---|---|
secretmessage boot |
essa |
| Sample Input 2 | Sample Output 2 |
|---|---|
treetreetreetree wood |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
oranges apples |
0 |
| Sample Input 4 | Sample Output 4 |
|---|---|
archipelago submarine |
2 |
