130
правок
Изменения
Добавил формальное определение
{{Определение
|definition = '''Z-функция''' от строки <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-функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки.[[Файл:Zfunc-examp.png|500px]]
}}
'''Примечание:''' далее в конспекте символы строки нумеруются с нуля.
[[Файл:Zfunc-examp.png|500px]]
== Тривиальный алгоритм ==
'''int'''[] zFunction('''string''' s)
'''int'''[] zf = '''int'''[n]
'''for''' i = 1 .. n - − 1
'''while''' i + zf[i] < n '''and''' s[zf[i]] == s[i + zf[i]]
zf[i]++
