ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Graveyard in Deyja

Time limit: 0.5 second
Memory limit: 64 MB
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 ≤ mn ≤ 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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1861. Graveyard in Deyja