http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=92.100.177.90&*Викиконспекты - Вклад участника [ru]2026-04-27T13:21:15ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F&diff=22835Z-функция2012-05-28T18:23:12Z<p>92.100.177.90: /* Время работы */</p>
<hr />
<div>==Определение==<br />
Z-функция от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>. Значение <tex>Z[0]</tex> не определено, поэтому его обычно приравнивают к нулю или к длине строки.<br />
[[Файл:Zfunc-examp.png|600px]]<br />
<br />
==Алгоритм поиска==<br />
Для работы алгоритма заведём две переменные: <tex>left</tex> и <tex>right</tex> — начало и конец наибольшего префикса строки <tex>S</tex> с максимальным значением <tex>right</tex>. Изначально <tex>left=0</tex> и <tex>right=0</tex>.<br />
<br />
Пусть нам известны значения Z-функции от <tex>0</tex> до <tex>i-1</tex>. Найдём <tex>Z[i]</tex>. <br />
Рассмотрим два случая.<br />
<br />
<br><br />
1) <tex>i > right</tex>:<br><br />
Просто пробегаемся по строке <tex>S</tex> и сравниваем символы на позициях <tex>S[i+j]</tex> и <tex>S[j]</tex>.<br />
Пусть <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>. <br />
<br />
<br><br />
2) <tex>i \le right</tex>:<br><br />
Сравним <tex>Z[i - left] + i</tex> и <tex>right</tex>. Если <tex>right</tex> меньше, то надо просто пробежаться по строке начиная с позиции <tex>right</tex> и вычислить значение <tex>Z[i]</tex>. <br />
Иначе мы уже знаем значение <tex>Z[i]</tex>, так как оно равно значению <tex>Z[i - left]</tex>.<br><br />
[[Файл:z-func.png]]<br />
<br />
==Время работы==<br />
Этот алгоритм работает за <tex>O(\lvert S\rvert)</tex>, так как каждая позиция пробегается не более двух раз: при попадании в диапазон от <tex>left</tex> до <tex>right</tex> и при высчитывании <tex>Z</tex>-функции простым циклом.<br />
<br />
==Псевдокод==<br />
'''Zfunction'''(p) <br />
answer[0] = 0<br />
left = 0<br />
right = 0<br />
'''for''' (i = 1..(n - 1))<br />
'''if''' (i > right)<br />
j = 0<br />
'''while''' (i + j < n && p[i + j] == p[j])<br />
j++<br />
answer[i] = j<br />
left = i<br />
right = i + j - 1<br />
'''else if''' (answer[i - left] < right - i + 1)<br />
answer[i] = answer[i - left]<br />
'''else''' <br />
j = 1<br />
'''while''' (j + right < n && p[j + right - i] == p[right + j])<br />
j++<br />
answer[i] = right + j - i<br />
left = i<br />
right = right + j - 1<br />
'''return''' answer<br />
<br />
== Источники ==<br />
[http://habrahabr.ru/post/113266/ Поиск подстроки и смежные вопросы — Хабр]<br><br />
[http://ru.wikipedia.org/wiki/Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Z-функция — Википедия]</div>92.100.177.90http://neerc.ifmo.ru/wiki/index.php?title=Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F&diff=22833Z-функция2012-05-28T18:16:02Z<p>92.100.177.90: /* Псевдокод */</p>
<hr />
<div>==Определение==<br />
Z-функция от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>. Значение <tex>Z[0]</tex> не определено, поэтому его обычно приравнивают к нулю или к длине строки.<br />
[[Файл:Zfunc-examp.png|600px]]<br />
<br />
==Алгоритм поиска==<br />
Для работы алгоритма заведём две переменные: <tex>left</tex> и <tex>right</tex> — начало и конец наибольшего префикса строки <tex>S</tex> с максимальным значением <tex>right</tex>. Изначально <tex>left=0</tex> и <tex>right=0</tex>.<br />
<br />
Пусть нам известны значения Z-функции от <tex>0</tex> до <tex>i-1</tex>. Найдём <tex>Z[i]</tex>. <br />
Рассмотрим два случая.<br />
<br />
<br><br />
1) <tex>i > right</tex>:<br><br />
Просто пробегаемся по строке <tex>S</tex> и сравниваем символы на позициях <tex>S[i+j]</tex> и <tex>S[j]</tex>.<br />
Пусть <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>. <br />
<br />
<br><br />
2) <tex>i \le right</tex>:<br><br />
Сравним <tex>Z[i - left] + i</tex> и <tex>right</tex>. Если <tex>right</tex> меньше, то надо просто пробежаться по строке начиная с позиции <tex>right</tex> и вычислить значение <tex>Z[i]</tex>. <br />
Иначе мы уже знаем значение <tex>Z[i]</tex>, так как оно равно значению <tex>Z[i - left]</tex>.<br><br />
[[Файл:z-func.png]]<br />
<br />
==Время работы==<br />
Этот алгоритм работает за <tex>O(\lvert S\rvert)</tex>, так как каждая позиция пробегается не более двух раз: при попадании в диапазон от <tex>left</tex> до <tex>right</tex> и при высчитывании Z-функции простым циклом.<br />
<br />
==Псевдокод==<br />
'''Zfunction'''(p) <br />
answer[0] = 0<br />
left = 0<br />
right = 0<br />
'''for''' (i = 1..(n - 1))<br />
'''if''' (i > right)<br />
j = 0<br />
'''while''' (i + j < n && p[i + j] == p[j])<br />
j++<br />
answer[i] = j<br />
left = i<br />
right = i + j - 1<br />
'''else if''' (answer[i - left] < right - i + 1)<br />
answer[i] = answer[i - left]<br />
'''else''' <br />
j = 1<br />
'''while''' (j + right < n && p[j + right - i] == p[right + j])<br />
j++<br />
answer[i] = right + j - i<br />
left = i<br />
right = right + j - 1<br />
'''return''' answer<br />
<br />
== Источники ==<br />
[http://habrahabr.ru/post/113266/ Поиск подстроки и смежные вопросы — Хабр]<br><br />
[http://ru.wikipedia.org/wiki/Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Z-функция — Википедия]</div>92.100.177.90