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

Поиск шаблона

Поиск шаблона

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

Строка состоит из символов двух непересекающихся алфавитов А_1 и А_2. Две строки будут равны, если существует взаимно-однозначное отображение символов из алфавита А_1 в символы алфавита А_2, после применения которого к одной из строк, строки будут совпадать.

При таком определении равенства строк будем говорить, что для заданного шаблона существует его вхождение в строку, если в строке найдется подстрока, равная этому шаблону.

Для заданных строки и шаблона необходимо посчитать количество вхождений этого шаблона в строку.

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

В первой строке входного файла записано два целых числа N и M — количество символов в первом и во втором алфавитах соответственно (1N, M < 52).

В следующих двух строках записаны без пробелов символы из алфавитов A_1 и A_2. Символами из алфавитов могут быть строчные и прописные латинские буквы.

Четвертая строка содержит строку, а пятая — шаблон. Длины строки и шаблона не превышают 10^5.

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

В выходной файл необходимо вывести одно целое число — количество вхождений шаблона в строку.

Пример

Входные данные #1
8 4
aIbctlyd
eouh
Itellyeh
you
Выходные данные #1
1
Источник Очный тур XIII Открытой Всесибирской олимпиады по программированию имени И.В. Поттосина