Вхождения с перекрытием

Даны строка и подстрока. Сколько раз подстрока встречается в строке, если вхождения могут перекрываться?

Например, в aaaa подстрока aa встречается три раза.

В первой строке — строка длиной от $1$ до $10^5$ символов. Во второй — подстрока длиной от $1$ до $100$. Обе состоят из строчных латинских букв.

Одно число.

Метод count считает только неперекрывающиеся вхождения, поэтому здесь он не подойдёт — нужен перебор начал со срезом.