Изменения

Перейти к: навигация, поиск

Z-функция

4 байта убрано, 17:26, 28 июня 2011
Нет описания правки
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()];
Анонимный участник

Навигация