Изменения

Отметим, что из-за символа <tex>\$</tex> значение <tex>\pi(k) \leq t</tex> для всех <tex>k</tex>. По определению <tex>\pi()</tex>, если <tex>\pi(k) = t</tex>, то <tex>P[0..t - 1] = P[k - t + 1..k]</tex>, то есть <tex>T = S[k - t - t..k - t - 1]</tex>, то есть <tex>T</tex> входит в <tex>S</tex>, начиная с позиции <tex>k - t - t</tex>. Пусть теперь <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>\pi()</tex> для <tex>P</tex>) + <tex>O(s)</tex>(последующий <tex>for</tex>) <tex>= O(s + t)</tex>.*'''Оценка по памяти''' Предложенная реализация имеет оценку по памяти <tex>O(S+T)</tex>. Оценки <tex>O(S)</tex> можно добиться за счет не запоминания значений <tex>pi()</tex> для позиций в <tex>P</tex> меньших <tex>t + 1</tex> (т.е. до начала цепочки <tex>S</tex>)