Задача B. Число вхождений подстроки

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Пусть имеется текстовая строка S, состоящая из произвольных печатных символов (ASCII 32-126). Требуется определить общее число ее подстрок, совпадающих с некоторым заданным образцом T.

Для решения задачи следует воспользоваться алгоритмом Кнута-Морриса-Пратта.

Формат входного файла

В заголовке входного файла "input.txt" содержится строка T, выступающая в роли образца. Далее следует строка S, в которой необходимо выполнить поиск.

Формат выходного файла

Выходной файл "output.txt" должен содержать число найденных подстрок.

Ограничения

0 < |T| ≤ 5 ⋅ 104, 0 ≤ |S| ≤ 2 ⋅ 107

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
ABCDEF
123 AB ABCDEFABCDEF ABCDEF45ABCDEFuZ
4
2
ABCABC
ZEt AB ABCABCABCABC ABC45-ABCABCABC+
5

0.108s 0.016s 15