Изменения

Z-функция от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>.

==Алгоритм поиска==

Дана строка <tex>S</tex>. Необходимо построить массив <tex>Z</tex>, такой что <tex>Z[i]</tex> является префикс функцией данной строки с позиции <tex>i</tex>

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

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

Этот алгоритм работает за <tex>O(\lvert S\rvert)</tex>, так как каждая позиция пробегается не более двух раз: при попадании в диапазон от <tex>left</tex> до <tex>right</tex> и при высчитывании Z-функции простым циклом.

int[] z(String p) {

int[] ans = new int[p.length()];