Enigma
InterviewTime limit2sMemory limit512 MB
Count alignments of the crib inside the ciphertext where no crib letter equals the ciphertext letter at the same offset.
- Level
Easy3 of 10
- Topics
- String, Brute force, Implementation
- Solved
- No attempts yet
Problem
The German encryption machine Enigma, used in World War II, replaced each letter typed on its keyboard with some other letter according to a given initial configuration. The substitution was quite complex, but the machine had a vulnerability: no letter was ever replaced by itself. Alan Turing exploited this vulnerability while working on cryptanalysis of the Enigma during the war. The goal was to find the machine's initial configuration by assuming the message contained a common phrase from communications, such as the word ARMADA. Such phrases were called cribs.
If the ciphertext was, for example, FDMLCRDMRALF, the work of testing possible machine configurations was simplified because the word ARMADA, if it appeared in that ciphertext, could only be in two positions, marked with arrows in the table below. The other five positions could not correspond to the crib ARMADA because at least one letter of the crib, underlined in the table below, matches its counterpart in the ciphertext. Since Enigma never replaced a letter with itself, those five positions could be discarded from testing.
In this problem, given a ciphertext and a crib, your program must compute the number of possible positions for the crib in the ciphertext.
Input
The first line of the input contains the ciphertext, a string of at least one and at most 104 letters. The second line contains the crib, a string of at least one letter and at most the same number of letters as the ciphertext. Only the 26 uppercase letters, without accents, appear in the ciphertext and the crib.
Output
Print one line containing an integer, the number of possible positions for the crib in the ciphertext.