Z-функция

Дана непустая строка s, длина которой N не превышает 10⁶. Будем считать, что элементы строки нумеруются от 1 до N.

Для каждой позиции i символа в строке определим Z-блок как наибольшую подстроку, которая начинается в этой позиции и совпадает с некоторым началом всей строки s. Значением Z-функции Z(i) будем считать длину этого Z-блока. (Заметим, что для первой позиции строки  Z-блок совпадает со всей строкой, поэтому Z(1)=N. С другой стороны, если s[i]≠s[1], то Z(i)=0).

Z-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск по образцу»).

Требуется для всех i от 1 до N вычислить Z(i).