Lich Sandro was alone at the ancient graveyard. The rulers of Deyja, and great
necromancers, and liches, who died during the wars with elves, were buried
there. Both ages and rigorous northern climate were ruthless to gravestones and
monuments, some of them were broken in pieces, others were covered with
fractures.
One of the graves amazed Sandro. It was astonishingly big and was situated at
the center of the graveyard, it looked like someone very important in the
history of Deyja was buried here. Maybe it was the first king of liches
himself. Sandro wants to check if the writing on the gravestone contains the
name of the first king. But the writing is difficult to read, only some letters
could be recognized. Help Sandro use the recognizable letters to decide if his
hypothesis can be true.
Input
The first line contains a string of length n consisting of English letters
and question marks. It represents the writing on the gravestone (question marks
denote letters that can't be recognized). The second line contains a string of
length m consisting of English letters.
It represents the name of the first king of liches.
It is guaranteed that 1 ≤ m ≤ n ≤ 1000.
Output
Output one integer: the maximal number of times the name of the first king
could possibly be encountered in the writing
when all the letters were recognizable.
The occurrences of the name may overlap.
String comparison must be case-sensitive.
Samples
input | output |
---|
R?la?dDefe?tedHi?Br?t?erArc?i??ld
Archibald
| 1
|
Arch?????rchibaldIronfist
Archibald
| 1
|
Problem Author: Mikhail Rubinchik
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011