У Берляндии невероятно богатая и славная история. Чтобы повысить уровень осведомленности о ней среди молодого поколения, Король Берляндии распорядился сочинить гимн.
Несмотря на то, что в прошлом у Берляндии было огромное множество достойных побед, есть одна наиболее важная. Король желает упомянуть ее в гимне как можно большее количество раз.
Он уже сочинил немалую часть гимна, осталось лишь заполнить некоторые места, которые ему никак не удаются. Король просит вас помочь с его работой.
Гимн Берляндии — это строка s, состоящая из не более чем 105 строчных латинских букв и знаков вопроса. Самая важная победа — это строка t, состоящая из не более чем 105 строчных латинских букв. Необходимо заменить все знаки вопроса строчными латинскими буквами так, чтобы максимизировать количество вхождений строки t в s.
Обратите внимание, что вхождения строки t в s могут пересекаться. В третьем примере рассмотрен такой случай.
Первая строка содержит строку из строчных латинских букв и знаков вопроса s (1 ≤ |s| ≤ 105).
Вторая строка содержит строку из строчных латинских букв t (1 ≤ |t| ≤ 105).
Произведение длин строк |s|·|t| не превосходит 107.
Выведите максимальное количество вхождений строки t, которое можно достичь, заменив все знаки вопроса в строке s не строчные латинские буквы.
winlose???winl???w??
win
5
glo?yto?e??an?
or
3
??c?????
abcab
2
В первом примере полученная строка s — "winlosewinwinlwinwin"
Во втором примере полученная строка s — "glorytoreorand". Последняя буква в строке может быть выбрана произвольно.
В третьем примере вхождения строки t пересекаются между собой. Строка s с максимальным количеством вхождений t — "abcabcab".
| Educational Codeforces Round 21 |
|---|
| Закончено |
