06/04/2025 22:48:29

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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