Изменения

Дана цепочка <tex>ST</tex> и образец <tex>TP</tex>. Требуется найти все позиции, начиная с которых <tex>TP</tex> входит в <tex>ST</tex>.

Построим строку <tex>S = P = T\#ST</tex>, где <tex>\#</tex> — любой символ, не входящий в алфавит <tex>SP</tex> и <tex>T</tex>. Посчитаем на ней [[Префикс-функция|префикс-функцию]] <tex>\pi()</tex>. Благодаря разделительному символу <tex>\#</tex>, выполняется <tex>\forall i: \pi(i) \le |T|</tex>. Заметим, что по определению [[Префикс-функция|префикс-функции]] при <tex>i > |TP|</tex> и <tex>\pi(i) = |TP|</tex> подстроки длины <tex>TP</tex>, начинающиеся с позиций <tex>0</tex> и <tex>i - |TP| + 1</tex>, совпадают. Соберем все такие позиции <tex>i - |TP| + 1</tex> строки <tex>PS</tex>, вычтем из каждой позиции <tex>|TP| + 1</tex>, это и будет ответ.