Изменения

Есть два случая: <tex>i > right</tex> и <tex>i \leq right</tex>.

Пусть <tex>j</tex> первая позиция в строке <tex>S</tex> для которой не выполняется равенство <tex>S[i+j] == S[j]</tex>, тогда <tex>j</tex> это и Z-функция для позиции <tex>i</tex>. Тогда <tex>left = i, right = i + j - 1</tex>.

Иначе мы уже знаем значение <tex>Z[i]</tex>, так как оно равно значению <tex>Z[i - left]</tex>.

===Время работы алгоритма===