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>
=== Псевдокод ===
'''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]++
'''return''' zf
'''int'''[] zf = '''int'''[n]
'''int''' left = 0, right = 0
'''for''' i = 0 1 .. 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]++
'''if''' i + zf[i] >= right
== Поиск подстроки в строке с помощью Z-функции ==
<tex>n</tex> — длина текста. <tex>m</tex> — длина образца. <br> Образуем строку <tex>s = needle + "\#" + source</tex>, где <tex>\#</tex> — символ, не встречающийся ни в <tex>source</tex>, ни в <tex>needle</tex>. Вычисляем Z-функцию от этой строки. В полученном массиве, в позициях в которых значение zZ-функции равно <tex>length(needle)</tex>, по определению начинается подстрока, совпадающая с <tex>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
