ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1861. Кладбище в Дейе

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Лич Сандро нашёл уединение на древнем кладбище, где были захоронены повелители Дейи, а также великие некроманты и личи, погибшие во время войн с эльфами. Время и суровый северный климат не пощадили памятники и надгробья — многие из них совсем развалились, другие ещё стояли, но были сильно обшарпаны.
Одна из гробниц поразила Сандро. Судя по её грандиозным размерам и расположению в центральной части кладбища, в ней был похоронен один из самых влиятельных персонажей в истории Дейи, возможно, даже сам первый король личей. Сандро подошёл к могильной плите, чтобы проверить, встречается ли в надписи на ней имя первого короля личей. Но надпись на плите почти полностью стёрлась, и разобрать на ней можно было лишь отдельные буквы. Сандро хочет определить по сохранившимся буквам, может ли быть верна его гипотеза.

Исходные данные

В первой строке дан полный текст надписи — строка длины n из латинских букв и знаков вопроса (знаки вопроса обозначают те буквы, которые не удалось разобрать). Во второй строке дано имя первого короля личей — строка длины m, состоящая из латинских букв. 1 ≤ mn ≤ 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