Изменения
→Описание алгоритма
{{Определение
|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}ldots \, i + k] = s[0 \mathinner{\ldotp\ldotp} ldots k]</tex>. <!-- проинлайнил \twodots из clrscode -->
Значение Z-функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки.
'''while''' i + zf[i] < n '''and''' s[zf[i]] == s[i + zf[i]]
zf[i]++
'''if''' i + zf[i] >= right
left = i
right = i + zf[i]
|definition= Необходимо восстановить строку по Z-функции, считая алфавит ограниченным.
}}
===Описание алгоритма===
Пусть в массиве <tex>z</tex> хранятся значения Z-функции, в <tex>s</tex> будет записан ответ. Пойдем по массиву <tex>z</tex> слева направо.
Нужно узнать значение <tex>s[i]</tex>. Для этого посмотрим на значение <tex>z[i]</tex>: если <tex>z[i] = 0</tex>, тогда в <tex>s[i]</tex> запишем ещё не использованный символ или последний использованный символ алфавита, если мы уже использовали все символы. Если <tex>z[i] \neq 0</tex>, то нам нужно записать префикс длины <tex>z[i]</tex> строки <tex>s</tex>. Но если при посимвольном записывании этого префикса в конец строки <tex>s</tex> мы нашли такой <tex>j</tex> (индекс последнего символа строки), что <tex>z[j]</tex> больше, чем длина оставшейся незаписанной части префикса, то мы перестаём писать этот префикс и пишем префикс длиной <tex>z[j]</tex> строки <tex>s</tex>.
Для правильной работы алгоритма, будем считать значение <tex>z[0]</tex> равным нулю.
Заметим, что не всегда удастся восстановить строку с ограниченным алфавитом неподходящего размера. Например, для строки <tex>abacaba</tex> массив Z-функций будет <tex>[0, 0, 1, 0, 3, 0, 1]</tex>. Используя двоичный алфавит, мы получим строку <tex>abababa</tex>, но её массив Z-функций отличается от исходного. Ошибка восстановления строки возникла, когда закончились новые символы алфавита.
Если строить строку по некорректному массиву значений Z-функции, то мы получим какую-то строку, но массив значений Z-функций от неё будет отличаться от исходного.
=== Время работы ===
Этот алгоритм работает за O(|S|), так как мы один раз проходим по массиву Z-функций.
=== Реализация ===
'''string''' buildFromZ(z : '''int'''[], alphabet : '''char'''[]):
'''string''' s = ""
Пусть <tex>z</tex> — данная Z-функция, строку <tex>s</tex> построил наш алгоритм, <tex>q</tex> — массив значений Z-функции для <tex>s</tex>. Покажем, что массивы <tex>q</tex> и <tex>z</tex> будут совпадать.
[[Файл: Запись_префикса.png|330px|thumb|right|Записали префикс, начинающийся в <tex>i</tex>. После пишем префикс, начинающийся в <tex>j</tex>. Этот префикс не изменит символы первого префикса.]] Рассмотрим похожий алгоритм, но с более худшей асимптотикой. Отличие будет в том, что при <tex>z[i] > 0</tex> мы будем писать префикс полностью и возвращаться в позицию <tex>i + 1</tex>. Рассмотрим каждый шаг этого алгоритма. Если <tex>z[i] = 0</tex>, то мы пишем символ, отличный от первого символа строки, поэтому <tex>q[i] = 0</tex>, а значит <tex>q[i] = z[i]</tex>. Если <tex>z[i] > 0</tex>, то при записи <tex>s[i]</tex> мы будем получать <tex>q[i] = z[i]</tex>, потому что мы переписали префикс строки. Но далее мы можем переписать этот префикс другим префиксом. ДопустимЗаметим, что новый префикс будет содержаться и в этом случае мы заменим некоторые символы на другиепрефиксе самой строки, поэтому пересечение двух префиксов будет состоять из одинаковых символов. Значит, префикс не будет изменяться, как и значение <tex>q[i]</tex>. Тогда массив <tex>q</tex> совпадает с <tex>z</tex> был некорректный. Значит, мы не изменяем префикс, когда пишем другой префикс, пересекающийся с ним, поэтому с помощью этого алгоритма мы получим строку с Z-функцией, совпадающей с заданной.
Покажем, что этот алгоритм эквивалентен нашему алгоритму. Когда мы пишем разные префиксы, то возможны три варианта: они не пересекаются(начало и конец одного префикса не принадлежат другому), один лежит внутри другого(начало и конец префикса принадлежит другому), они пересекаются(начало одного префикса пренадлежит другому, но конец не принадлежит).* Если префиксы не пересекаются, то в алгоритме они не влияют друг на друга.[[Файл: Префиксы1.png|400px]]* Если префикс лежит внутри другого префикса, то записав большой префикс мы запишем и малый, поэтому не нужно возвращаться к началу малого префикса.[[Файл: Префиксы2.png|400px]]* Если префиксы пересекаются, то нам нужно переписать часть первого префикса , который начинается раньше, и начать писать другой префикс (начало этого префикса запишет конец префикса, начинающегося раньше). Если полностью второй переписать префикс, начинающийся раньше, то мы не сможем восстановить префикс, который начинался раньше конца первого префикса.[[Файл: Префиксы3.png|400px]]
Таким образом, алгоритмы эквивалентны и наш алгоритм тоже корректен.
==Построение Z-функции по префикс-функции==
{{Задача
|definition= Дан массив с корректной [[Префикс-функция | префикс-функцией]] для строки <tex>s</tex>, . Требуется получить массив с Z-функцией для строки <tex>s</tex>.
}}[[Файл:Case one.png|300px|thumb|right|'''Случай первый''']]
[[Файл:Case two.png|300px|thumb|right|'''Случай второй''']]
===Описание алгоритма===
<br>
Пусть префикс функция хранится в массиве <tex>P[0 ... \ldots n - 1]</tex>. Z-функцию будем записывать в массив <tex>Z[0 ... \ldots n-1]</tex>. Заметим, что если <tex>P[i]>0</tex>, то мы можем заявить, что <tex>Z[i-P[i]+1]</tex> будет не меньше, чем <tex>P[i]</tex>.
<br>
<br>
<br>
<br>
Пусть в <tex>Z[i] = z > 0</tex>, рассмотрю <tex>j<z</tex>, <tex>Z[j]=k</tex> и <tex>Z[i+j]=k_1</tex>. ЗаметимПусть <tex>b_1=s[0 \ldots k-1]</tex>, <tex>b_2=s[j \ldots j+k-1]</tex>, что <tex>b_3=s[0 ... \ldots z-1]</tex> совпадает с . Тогда заметим, что <tex>b_3 = s[i...\ldots i+z-1]</tex> и тогда возможны три случая:
# <tex>k<k_1</tex>.
#: Тогда <tex>b_1 \subset s[0...k-1]</tex> {{---}} это подстрока <tex>s[0...k_1-1]</tex>, но <tex>s[0...\ldots k_1-1]</tex> равна <tex>=s[i+j...\ldots i+j+k_1-1]</tex> и тогда очевидно, что мы не можем увеличить значение <tex>Z[i+j]</tex> и надо рассматривать уже <tex>i=i+j</tex>.
# <tex>k<z-j</tex> и <tex>k>k_1</tex>.
#: Тогда <tex>s[0...k-1]</tex> равна <tex>s[j...j+k-1]</tex>, которая является подстрокой строки <tex>s[0...z-1]</tex>, которая равна <tex>b_1 = b_2 \subset b_3 = s[i...\ldots i+z-1]</tex>. Значит точно можно сказать, что <tex>s[0...k-1]</tex> равна <tex>\Rightarrow b_1 = s[i+j...\ldots i+j+k-1]</tex> и тогда очевидно, что <tex>Z[i+j]</tex> можно увеличить до <tex>k</tex>.
# <tex>k>z-j</tex> и <tex>k>k_1</tex>.
#: Тогда <tex>s[0...k-1]b_1 = b_2 </tex> равна , но <tex>s[j...j+k-1]b_2</tex>, которая не является подстрокой строки <tex>s[0...z-1]b_3</tex> (так как<tex>j+k-1 > z</tex>). Так как известно, что <tex>s[z]</tex> не равен <tex> \ne s[i+z]</tex>, то равны лишь <tex>s[0...\ldots z-j]</tex> и <tex>= s[i+j...\ldots i+z-1]</tex> и тогда понятно, что <tex>Z[i+j]=z-j</tex>.
<br>
===Псевдокод===
'''int[]''' buildZFunctionFromPrefixFunction(P : '''int'''[n])
'''int'''[] Z = '''int'''[n]
'''for''' i = 1 '''to''' n - 1
Z[i - P[i] + 1] = P[i]
Z[0] = n
'''int''' ti = 1 '''forwhile''' i = 1 < n '''toint''' n - 1 t = i
'''if''' Z[i] > 0
'''for''' j = 1 '''to''' Z[i] - 1
Z[i + j] = min(Z[j], Z[i] - j)
t = i + j
i = t+ 1
'''return''' Z
===Время работы===
== См. также ==
