bng453

30.12.2020 10:21

Информатика

Есть ответ 👍

Задача 3: Не был предателем... Гриша уже несколько несколько недель отрабатывает свои навыки в новомодной онлайн-игре про команду космического корабля, вычисляющую предателей среди них. Так как игра очень популярна, появились игроки, которые договариваются между собой о каких-то коммуницировать заранее. Таких людей называют заговорщиками.

Заговорщики действуют по следующему алгоритму. В начале игры каждый из заговорщиков пишет в общий чат строку T — ключ шифрования. Далее в течение игры игрок придумывает строку S, записывает её N раз подряд и отправляет в чат. Для того, чтобы получить зашифрованное сообщение, остальным заговорщикам нужно посчитать, сколько раз в этой повторённой N раз строке S встречается ключ шифрования T. Чат обновляется слишком быстро и Гриша не успевает это сделать руками Грише решить эту задачу.

Входные данные
В первой строке входных данных записана строка T, содержащая не более 300 символов — ключ шифрования.

Во второй строке записана строка S, её длина также не превосходит 300.

В третьей строке записано целое число N, 1 ≤ N ≤ 5×106 — количество повторений строки S.

Все строки состоят только из заглавных английских букв.

Выходные данные
Программа должна вывести единственное целое число — количество вхождений строки T в строку S, повторённую N раз. Под одним вхождением подразумевается один выбрать подстроку, то есть несколько подряд идущих символов строки, совпадающих со строкой T, не меняя порядок следования этих символов.

Система оценивания
Решения, правильно работающие, когда длины строк T и S, а также число N не превосходят 100, будут оцениваться в