405335: GYM101908 E Enigma

Given an initial configuration, the World War II German encryption machine Enigma replaces each letter typed on the keyboard with some other letter. The replacement strategy was quite complex, but the machine had a vulnerability: a letter would never be replaced by itself! This vulnerability was exploited by Alan Turing, who worked in the cryptanalysis of Enigma during the war. His goal was to find the initial configuration of the machine using the assumption that the message contained a certain usual expression of communication, such as the word ARMADA, for example. These expressions were called cribs. If the message FDMLCRDMRALF was encrypted, for example, the process of testing the possible configurations of the machine would be simpler because the word ARMADA, if present in the encrypted message, could only be in two positions, illustrated in the table below with an arrow. The remaining five positions could not match the crib ARMADA because at least one letter in the crib, underlined in the table below, would match its correspondent in the encrypted message; as the machine would never replace a letter by itself, these five positions could be ignored in the tests.

In this problem your program should compute, given a ciphertext and a crib, the number of possible positions for the crib in the encrypted message.

The first line of the input contains the encrypted message, which is a sequence of at least one letter and a maximum of $$$10^4$$$ letters. The second line of the input contains the crib, which is a sequence of at least one letter and at most the same number of letters of the message. Only the $$$26$$$ uppercase English letters appear on message and in the crib.

Print a line containing an integer, indicating the number of possible starting positions for the crib in the encrypted message.

FDMLCRDMRALF
ARMADA

2

AAAAABABABABABABABABA
ABA

7