1633: CF808 - G. Anthem of Berland
[Creator : ]
Description
Berland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem.
Though there are lots and lots of victories in history of Berland, there is the one that stand out the most. King wants to mention it in the anthem as many times as possible.
He has already composed major part of the anthem and now just needs to fill in some letters. King asked you to help him with this work.
The anthem is the stringsof no more than $10^5$ small Latin letters and question marks. The most glorious victory is the stringtof no more than $10^5$ small Latin letters. You should replace all the question marks with small Latin letters in such a way that the number of occurrences of string $t$ in string $s$ is maximal.
Note that the occurrences of string $t$ in $s$ can overlap. Check the third example for clarification.
He has already composed major part of the anthem and now just needs to fill in some letters. King asked you to help him with this work.
The anthem is the stringsof no more than $10^5$ small Latin letters and question marks. The most glorious victory is the stringtof no more than $10^5$ small Latin letters. You should replace all the question marks with small Latin letters in such a way that the number of occurrences of string $t$ in string $s$ is maximal.
Note that the occurrences of string $t$ in $s$ can overlap. Check the third example for clarification.
Input
The first line contains string of small Latin letters and question marks $s\ (1≤|s|≤10^5)$.
The second line contains string of small Latin letters $t\ (1≤|t|≤10^5)$.
Product of lengths of strings $|s|·|t|$ won't exceed $10^7$.
The second line contains string of small Latin letters $t\ (1≤|t|≤10^5)$.
Product of lengths of strings $|s|·|t|$ won't exceed $10^7$.
Output
Output the maximum number of occurrences of stringtyou can achieve by replacing all the question marks in stringswith small Latin letters.
Sample 1 Input
winlose???winl???w??
win
Sample 1 Output
5
the resulting string s is "winlosewinwinlwinwin"
Sample 2 Input
glo?yto?e??an?
or
Sample 2 Output
3
the resulting string s is "glorytoreorand". The last letter of the string can be arbitrary.
Sample 3 Input
??c?????
abcab
Sample 3 Output
2
occurrences of string t are overlapping. String s with maximal number of occurrences of t is "abcabcab".
HINT
相同题目：CF808G。