Изменения
Нет описания правки
==Алгоритм поиска==
===Задача===
Дана строка <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>S[i+j]</tex>. (и <tex>S[i+j] == S[j]</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>.
