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

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

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

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

Ограничение времени: 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
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1861. Кладбище в Дейе