Условие задачи: Данa строка s длины n. Нужно вычислить Z-функцию — массив z длины n, где z[i] равна максимальной длине подстроки, начинающейся с позиции i и совпадающей с префиксом строки.

Формат входных данных:
Первая строка — целое число n (1 ≤ n ≤ 1 000 000).
Вторая строка — сама строка s длины n (латиница, без пробелов).

Формат выходных данных: n чисел z[0] … z[n-1], разделённых пробелом (обычно z[0] = 0).

Решение: Мы поддерживаем окно [l…r], в котором уже найдено совпадение с префиксом. Для каждой позиции i сначала берем z[i] = min(r - i + 1, z[i-l]), если i ≤ r, чтобы не проверять заново уже известные символы. Затем «дотягиваем» совпадение наивным сравнением символов дальше. Если новая правая граница превосходит r, сдвигаем l, r.
В итоге, алгоритм работает за линейное время и память O(n).

После выполнения цикла в z будут все значения Z-функции.

Например,

даёт

Доказательство корректности: Инвариант: перед обработкой i окно [l…r] реально отражает максимум совпадения префикса, заканчивающегося не раньше r. При i≤r значение z[i-l] ― длина совпадения в зеркальной позиции, мы используем не больше чем гарантировано до r. Дальнейшее наивное расширение полностью проверяет оставшиеся символы. Для i>r мы начинаем сравнение с нуля, что корректно. Так все z[i] вычисляются без пропусков или переизбыточных проверок.