Сколько раз встречается образец

1000 мс · 256 МБ · всё или ничего

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

В первой строке - строка $S$ , во второй - строка $T$ . Обе непусты, из строчных латинских букв, длины не превосходят $5 \cdot 10^5$ .

Выведите количество вхождений $T$ в $S$ .

ввод

aaaa
aa

вывод

ввод

abc
xyz

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.