130
правок
Изменения
Стилистические правки
{{Определение
|definition = '''Z-функция''' (англ. ''Z-function'') от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>. Более формально, <tex>Z[i](s) = \max k \mid s[i\, \mathinner{\ldotp\ldotp}\, i + k] = s[0\, \mathinner{\ldotp\ldotp}\, k]</tex>. <!-- проинлайнил \twodots из clrscode -->
Значение Z-функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки.
=== Псевдокод ===
'''int'''[] zFunction(s : '''string''' s):
'''int'''[] zf = '''int'''[n]
'''for''' i = 1 .. '''to''' n − 1
'''while''' i + zf[i] < n '''and''' s[zf[i]] == s[i + zf[i]]
zf[i]++
=== Время работы ===
Этот алгоритм работает за <tex>O(\lvert |S\rvert|)</tex>, так как каждая позиция пробегается не более двух раз: при попадании в диапазон от <tex>left</tex> до <tex>right</tex> и при высчитывании Z-функции простым циклом.
=== Псевдокод ===
'''int'''[] zFunction(s : '''string''' s):
'''int'''[] zf = '''int'''[n]
'''int''' left = 0, right = 0
'''for''' i = 1 .. '''to''' n - − 1 zf[i] = '''max'''(0, '''min'''(right - − i, zf[i - − left]))
'''while''' i + zf[i] < n '''and''' s[zf[i]] == s[i + zf[i]]
zf[i]++
== Поиск подстроки в строке с помощью Z-функции ==
<tex>n</tex> — длина текста. <tex>m</tex> — длина образца. <br>
Образуем строку <textt>s = \texttt{needle} pattern + \# + \texttt{source}text</textt>, где <textt>\#</textt> — символ, не встречающийся ни в <textt>\texttt{source}text</textt>, ни в <textt>\texttt{needle}pattern</textt>. Вычисляем Z-функцию от этой строки.В полученном массиве, в позициях в которых значение Z-функции равно <tex>|\texttt{needlepattern}|</tex>, по определению начинается подстрока, совпадающая с <textt>\texttt{needle}pattern</textt>.
=== Псевдокод ===
'''int''' substringSearch(text : '''string''' source, pattern : '''string''' needle): '''int'''[] zf = zFunction(needle pattern + '#' + sourcetext) '''for''' i = m + 1 .. '''to''' n + m
'''if''' zf[i] == m
'''return''' i
