68
правок
Изменения
Нет описания правки
Дана строка <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-функции от <tex>0</tex> до <tex>i-1</tex>. Найдём <tex>Z[i]</tex>.
Есть два случая: <tex>i > right</tex> и <tex>i \leq right</tex>.
Пусть <tex>i > right</tex>. Тогда просто пробегаемся по строке <tex>S</tex> и сравниваем символы из начала с символами после позиции <tex>i</tex>. (<tex>S[i+j] == S[j]</tex>)
Пусть <tex>j</tex> первая позиция в строке <tex>S</tex> для которой не выполняется равенство <tex>S[i+j] == S[j]</tex>, тогда <tex>j</tx> это и Z-функция для позиции <tex>i</tex>. Тогда <tex>left = i, right = i + j - 1</tex>.
Если <tex>i \leq right</tex> и
*'''Код алгоритма'''
int[] z(String p) {
