Изменения

==Описание алгоритма==

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

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