34
правки
Изменения
Нет описания правки
==Определение==
Z-функция от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>. Значение <tex>Z</tex>-функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки.
[[Файл:Zfunc-examp.png|600px]]<br>
'''Примечание:''' далее в конспекте символы строки нумеруются с нуля.
==Алгоритм Тривиальный алгоритм == Простая реализация за <tex>O(n^2)</tex>. Для каждой позиции i перебираем для неё ответ, начиная с нуля, пока не обнаружим несовпадение или не дойдем до конца строки. === Псевдокод === '''int'''[] z_function('''string''' s) '''int'''[] zf '''for''' i = 1 .. '''length'''(s) '''while''' (i + zf[i] < '''length'''(s)) && (s[zf[i]] == s[i + zf[i]]) zf[i]++ '''return''' zf == Эффективный алгоритм поиска==
Z-блоком назовем подстроку с началом в позиции <tex>i</tex> и длиной <tex>Z[i]</tex>.<br>
Для работы алгоритма заведём две переменные: <tex>left</tex> и <tex>right</tex> — начало и конец Z-блока строки <tex>S</tex> с максимальной позицией конца <tex>right</tex> (среди всех таких Z-блоков, если их несколько, выбирается наибольший). Изначально <tex>left=0</tex> и <tex>right=0</tex>.
Рассмотрим два случая.
1) <tex>i > right</tex>:<br>
Просто пробегаемся по строке <tex>S</tex> и сравниваем символы на позициях <tex>S[i+j]</tex> и <tex>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>. В данном случае будет определено корректное значение <tex>Z[i]</tex> в силу того, что оно определяется наивно, путем сравнения с начальными символами строки.
2) <tex>i \le right</tex>:<br>
Сравним <tex>Z[i - left] + i</tex> и <tex>right</tex>. Если <tex>right</tex> меньше, то надо просто наивно пробежаться по строке начиная с позиции <tex>right</tex> и вычислить значение <tex>Z[i]</tex>. Корректность в таком случае также гарантированна.
[[Файл:z-func.png]]
===Время работы===
Этот алгоритм работает за <tex>O(\lvert S\rvert)</tex>, так как каждая позиция пробегается не более двух раз: при попадании в диапазон от <tex>left</tex> до <tex>right</tex> и при высчитывании <tex>Z</tex>-функции простым циклом.
===Псевдокод=== '''int'''Zfunction[] '''z_function'''(p'''string''' s) answer'''int'''[0] = 0zf '''int''' left = 0 , right = 0 '''for''' (i = 10 ..(n - 1)) '''iflength''' (i > rights) j zf[i] = 0 '''whilemax''' (i + j < n && p[i + j] == p[j]) j++ answer[i] = j left = i right = i + j - 1 0, '''else ifmin''' (answer[i - left] < right - i + 1) answer[i] = answer, zf[i - left])) '''elsewhile''' j = 1 (i + zf[i] < '''whilelength''' (j + right < n s))) && p(s[zf[j + right - i]] == ps[right i + jzf[i]]) j zf[i]++ answer '''if''' i + zf[i] >= right + j - i left = i right = right i + j - 1z[i] '''return''' answerzf
== Источники ==
[http://habrahabr.ru/post/113266/ Поиск подстроки и смежные вопросы — Хабр]<br>
[http[wikipedia://ru.wikipedia.org/wiki/:Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F функция | Википедия — Z-функция — Википедия]] [[Категория: Дискретная математика и алгоритмы]][[Категория: Поиск подстроки в строке]]
