Лич Сандро нашёл уединение
на древнем кладбище, где были захоронены повелители Дейи,
а также великие некроманты и личи, погибшие во время войн с эльфами.
Время и суровый северный климат не пощадили памятники и
надгробья — многие из них совсем развалились, другие
ещё стояли, но были сильно обшарпаны.
Одна из гробниц поразила Сандро. Судя по её грандиозным размерам
и расположению в центральной части кладбища,
в ней был похоронен один из самых влиятельных персонажей в истории Дейи,
возможно, даже сам первый король личей.
Сандро подошёл к могильной плите, чтобы проверить, встречается ли в
надписи на ней имя первого короля личей. Но надпись на плите почти полностью стёрлась, и
разобрать на ней можно было лишь отдельные буквы.
Сандро хочет определить по сохранившимся буквам, может ли быть
верна его гипотеза.
Исходные данные
В первой строке дан полный текст надписи — строка длины n из латинских букв
и знаков вопроса (знаки вопроса обозначают те буквы, которые не удалось
разобрать).
Во второй строке дано имя первого короля личей — строка длины
m, состоящая из латинских букв.
1 ≤ m ≤ n ≤ 1000.
Результат
Выведите единственное число — максимальное количество раз, которое могло
встречаться имя первого короля личей в тексте надгробной надписи, когда все буквы в ней были целы.
Вхождения имени короля в текст надписи могут пересекаться.
Строки, различающиеся регистром, следует считать различными.
Примеры
исходные данные | результат |
---|
R?la?dDefe?tedHi?Br?t?erArc?i??ld
Archibald
| 1
|
Arch?????rchibaldIronfist
Archibald
| 1
|
Автор задачи: Михаил Рубинчик
Источник задачи: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011