Поиск количества вхождения подстроки в строке
Как возможно определить количество вхождения подстроки в строку, если подстроки могут пересекаться? Например: в строку "ааа" подстрока "аа" должна входить 2 раза.
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Приписать к паттерну P спецсимвол, который не встречается ни в строке S, ни в паттерне P, потом приписать строку S (в которой нужно искать)
F = P + "#" + S
и построить для F префикс-функцию (Кнут, Моррис и Пратт на троих сообразили, как это сделать за линейное время).
Посчитать в значениях префикс-функции количество значений n=Len(P) для позиций больше n