C. Сколько вхождений

Посчитайте, сколько раз строка $T$ входит в строку $S$. Вхождения могут перекрываться.

Выводить сами позиции не нужно — только количество. Решение то же самое, что в классе: склейка $T + \# + S$ и подсчёт позиций, где префикс-функция равна $|T|$.

Проверьте себя на строках $S =$ aaaa, $T =$ aa: вхождений три, а не два. Перекрытия считаются.

Первая строка содержит строку $S$, вторая — строку $T$.

Длины больше нуля и меньше $500\,000$, строки состоят из строчных латинских букв.

Одно число — количество вхождений.