Изменения

Для работы алгоритма заведём две переменные: <tex>left</tex> и <tex>right</tex> — начало и конец наибольшего префикса строки <tex>S</tex> с максимальным значением <tex>right</tex>. Изначально <tex>left=0</tex> и <tex>right=0</tex>.

Есть два случая: <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>.

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