Задача №114434. Не был предателем...
Гриша уже несколько несколько недель отрабатывает свои навыки в новомодной онлайн-игре про команду космического корабля, вычисляющую предателей среди них. Так как игра очень популярна, появились игроки, которые договариваются между собой о каких-то способах коммуницировать заранее. Таких людей называют заговорщиками.
Заговорщики действуют по следующему алгоритму. В начале игры каждый из заговорщиков пишет в общий чат строку \(T\) — ключ шифрования. Далее в течение игры игрок придумывает строку \(S\), записывает её \(N\) раз подряд и отправляет в чат. Для того, чтобы получить зашифрованное сообщение, остальным заговорщикам нужно посчитать, сколько раз в этой повторённой \(N\) раз строке \(S\) встречается ключ шифрования \(T\). Чат обновляется слишком быстро и Гриша не успевает это сделать руками. Помогите Грише решить эту задачу.
В первой строке входных данных записана строка \(T\), содержащая не более 300 символов — ключ шифрования.
Во второй строке записана строка \(S\), её длина также не превосходит 300.
В третьей строке записано целое число \(N\), \(1\le N \le 5 \times 10^6\) — количество повторений строки \(S\).
Все строки состоят только из заглавных английских букв.
Программа должна вывести единственное целое число — количество вхождений строки \(T\) в строку \(S\), повторённую \(N\) раз. Под одним вхождением подразумевается один способ выбрать подстроку, то есть несколько подряд идущих символов строки, совпадающих со строкой \(T\), не меняя порядок следования этих символов.
Решения, правильно работающие, когда длины строк \(T\) и \(S\), а также число \(N\) не превосходят 100, будут оцениваться в 60 баллов.
Пояснение ко второму примеру. Если строку BABA повторить 3 раза, получится BABABABABABA. В полученной строке подстрока ABA встречается 5 раз: B ABA BABABABA, BAB ABA BABABA, BABAB ABA BABA, BABABAB ABA BA, BABABABAB ABA .
MON AMONGUS 3
3
ABA BABA 3
5