eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Соответствие шаблону

Соответствие шаблону

Лимит времени 5 секунд
Лимит использования памяти 256 MiB

Назовём шаблоном непустую строку, состоящую только из маленьких латинских букв и специальных символов '*' (звёздочек).

Будем говорить, что строка Tсоответствует шаблону P тогда и только тогда, когда можно заменить звездочки в P на любые последовательности маленьких латинских символов (возможно, пустые) и в итоге получить строку T. Так, строка aadbc соответствует шаблону a*b*c, поскольку мы можем для её получения первую звёздочку шаблона заменить на ad, а вторую — на пустую последовательность символов. С другой стороны, строка abcbcb этому шаблону не соответствует.

Задана непустая строка S из маленьких латинских букв. Найдите количество циклических сдвигов этой строки, которые соответствуют шаблону P.

Входные данные

В первой строке входного файла записан шаблон P (длиной от 1 до 100 символов). Во второй строке задаётся S (длиной от 1 до 100000 символов).

Выходные данные

Выведите единственное число — количество циклических сдвигов строки S, которые соответствуют шаблону P.

Пример

Входные данные #1
aaaa
aaaa
Выходные данные #1
4
Источник NEERC Western Subregional Contest 2012