Изменения

Пусть теперь <tex>T</tex> входит в <tex>S</tex>, начиная с позиции <tex>i</tex>. Тогда <tex>S[i..i + t - 1] = T[0..t - 1]</tex>. Иными словами, <tex>P[0..t - 1] = P[t + 1 + i..t + i + t]</tex>, что эквивалентно <tex>\pi(t + i + t) = t</tex>.

==Время работы==

==Оценка по памяти==

Предложенная реализация имеет оценку по памяти <tex>O(S+T)</tex>. Оценки <tex>O(S)</tex> можно добиться за счет незапоминания значений <tex>\pi()</tex> для позиций в <tex>P</tex>, меньших <tex>t + 1</tex> (до начала цепочки <tex>S</tex>).