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''' substringSearch(text : '''string''', pattern : '''string'''):
'''int'''[] zf = zFunction(pattern + '#' + text)
'''for''' i = m + 1 '''to''' n + m1
'''if''' zf[i] == m
'''return''' i
