Изменения

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

Простая реализация за <tex>O(n^2)</tex>, где <tex>n</tex> — длина строки. Для каждой позиции <tex>i </tex> перебираем для неё ответ, начиная с нуля, пока не обнаружим несовпадение или не дойдем до конца строки.

<tex>n = length(s)</tex> '''int'''[] z_functionzFunction('''string''' s) '''int'''[] zf= '''int'''[n] '''for''' i = 1 .. '''length'''(s)n '''while''' (i + zf[i] < n) '''lengthand'''(s)) && (s[zf[i]] == s[i + zf[i]])

Пусть <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 leqslant right</tex>:<br>

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

<tex>n = length(s)</tex> '''int'''[] '''z_functionzFunction'''('''string''' s) '''int'''[] zf= '''int'''[n]

'''for''' i = 0 .. '''length'''(s)n zf[i] = '''max'''(0, '''min'''(right - i, zf[i - left])) '''while''' (i + zf[i] < n) '''lengthand'''(s))) && (s[zf[i]] == s[i + zf[i]])

== Поиск подстроки в строке с помощью Z-функции ==Образуем строку <tex>s = needle + '\#' + source</tex>, где <tex>'\#'</tex> — символ, не встречающийся ни в source, ни в needle. Вычисляем Z-функцию от этой строки. В полученном массиве, в позициях в которых значение z-функции равно length(needle), по определению начинается подстрока, совпадающая с needle.  === Псевдокод ===<tex>n = length(source)</tex> <br><tex>m = length(needle)</tex> '''int''' substringSearch('''string''' source, '''string''' needle) '''int'''[] zf = zFunction(needle + '#' + source) '''for''' i = m+1 .. n+m+1 '''if''' sf[i] == m '''return''' i == Источники информации ==* [http://habrahabr.ru/post/113266/ Поиск подстроки и смежные вопросы — Хабр]<br>* [[wikipedia:ru:Z-функция | Википедия — Z-функция]]