images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
20/04/2024 04:24:59

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2389. Тайная переписка

Ограничения: время – 1s/2s, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Ледяной Король похитил Принцессу и держит её в заточении. Принцесса пересылает регулярно сообщения Финну, используя следующий простой шифр. Сначала Принцесса в каждом появлении секретного слова, которое может вызвать гнев Ледяного Короля, заменяет `K` букв, идущих подряд, на случайные буквы. При этом существует вероятность, что буквы будут заменены на те же буквы. Затем она из текста убирает все пробелы и знаки препинания и заменяет все буквы на строчные.
Ледяной Король перехватил сообщение Принцессы и хочет узнать, сколько раз секретное слово возможно присутствует в сообщении.
Формат ввода
Первая строка ввода содержит одно целое число `T` (`1\ ≤\ T\ ≤\ 10`) — количество тестовых случаев. Каждый тестовый случай состоит из трёх строк. Первая строка содержит сообщение `M`, перехваченное Ледяным Королем (`1\ ≤\ |M|\ ≤\ 10^5`) . Вторая строка содержит секретное слово `S` (`1\ ≤\ |S|\ ≤\ |M|`). Третья строка содержит одно целое число `K` (`1\ ≤\ K\ ≤\ |S|`) – количество заменяемых букв. Сообщение и секретное слово содержат только строчные латинские буквы.
Формат вывода
Для каждого тестового случая вывести одно целое число — сколько раз секретное слово возможно встречается в сообщении. Возможные расположения секретного слова могут накладываться.

Пример ввода

3
ilcweyoufinnwithflameloveprincess
love
2
ahcahcahcahcahc
aha
1
yuoyuoyuoyuoyuo
you
2

Пример вывода

3
5
9
loading