Изменения

Рассмотрим два случая.

Просто пробегаемся по строке <tex>S</tex> и сравниваем символы на позициях <tex>S[i+j]</tex> и <tex>S[j]</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> в силу того, что оно определяется наивно, путем сравнения с начальными символами строки.

[[Файл:z-func.png]]

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