Изменения

*Нужно избавиться от явных сравнений строк. Пусть вычислено <tex>\pi(i-1)k</tex> и <tex>s[\pi(i{{--1) + 1] = s[i]</tex>, тогда <tex>\pi(i) = \pi(i-1) + 1</tex>. Если <tex>s[\pi(i) + 1] </tex> отличается от <tex>s[i]</tex>, то нужно найти наибольшую длину <tex> k</tex>}} наибольшая длина, для которой верно <tex>\pi(i) = k + 1</tex>. Когда найдется такое <tex>k</tex> достаточно будет сравнить <tex>s[k + 1]</tex> и <tex>s[i]</tex>, при их равенстве <tex>\pi(i) = k + 1</tex> будет верно. Итеративно В другом случае продолжается поиск <tex>k</tex>, пока оно больше нуля. Если <tex>k=0</tex>, то при <tex>\pi(i)=1</tex> в случае, когда <tex>s[i] = s[1]</tex> значение , иначе <tex>\pi(i)=10</tex> , иначе нулю. Общая схема алгоритма есть, теперь нужно научиться искать <tex>k</tex>.

Время работы алгоритма составит <tex>O(n)</tex>. Для доказательства этого потребуется новое обозначение <tex>w_i</tex> {{---}} количество итераций цикла <tex>while</tex> на <tex>i</tex>-ом шаге. Итоговое время работы алгоритма составит <tex>\sum\limits_{i=2}^n w_i</tex>. Теперь стоит отметить, что <tex>k</tex> увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение <tex>k = n - 1.</tex> . Внутри цикла <tex>while</tex> значение <tex>k</tex> лишь уменьшается, а из предыдущего утверждения получается, что оно не может уменьшиться больше, чем <tex>n-1</tex> раз, значит <tex>\sum\limits_{i=2}^n w_i \le n</tex>, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>.