146
правок
Изменения
Нет описания правки
==Построение строки по Z-функции==
{{Задача|definition===Постановка задачи===Восстановить строку по Z-функции за <tex>O(n)</tex>, считая алфавит ограниченным. Если нам нужен неограниченный алфавит, то будем считать, то мощность алфавита равна длине получаемой строки.}}
===Описание алгоритма===
Пусть в массиве <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> равным нулю.
Алгоритм всегда сможет построить строку по корректному массиву значений Z-функции, если в алфавите больше одного символа.
=== Реализация ===
'''string''' buildFromZ(z : '''int'''[], alphabet : '''char'''[]): '''string''' s = "a" '''int''' prefixLength = 1 0 <font color=green>// длина префикса, который мы записываем</font>
'''int''' j <font color=green>// позиция символа в строке, который будем записывать</font>
'''int''' newCharacter = 0 <font color=green>// индекс нового символа</font>
'''for''' i = 0 '''to''' z.length - 1
<font color=green>// мы не пишем какой-то префикс и не будем писать новый</font>
'''if''' z[i] = 0 '''and''' prefixLength = 0
if newCharacter < alphabet.length s += new character <font coloralphabet[newCharacter] newCharacter++ else s +=green>// если нового символа нет, то берём последний использованный</font>alphabet[newCharacter - 1]
<font color=green>// нам нужно запомнить, что мы пишем префикс </font>
'''if''' z[i] > prefixLength '''and'''
prefixLength = z[i]
j = 0
<font color=green>// пишем префикс</font>
'''if''' prefixLength > 0 '''and'''
s += s[j]
j++
Пусть <tex>z</tex> — данная Z-функция, строку <tex>s</tex> построил наш алгоритм, <tex>q</tex> — массив значений Z-функции для <tex>s</tex>.
Рассмотрим значения <tex>z[i] \ne 0</tex>. В этом случае мы писали префикс <tex>s[i]</tex> является началом префикса исходной строки. Назовём подстроку, его часть или данный префикс полностью содержался в другом префиксесовпадающую с некоторым префиксом строки, блоком. Возможны три положения блока, относительно других блоков. #Очевидно, что если мы записали префикс Он не пересекает другие блоки (но может полностью, включать в себя какой-то блок). Тогда <tex>q[i] = z[i]</tex>.#Если префикс лежит внутри другого префикса, который мы уже пишем, то этот же потому что наш алгоритм полностью скопирует префикс есть в префиксе исходной всей строки и Z-функции от него совпадают с Z-функциями рассматриваемого префикса (рассматривается первый случай).#Рассмотрим случай, когда мы записали часть префикса и прервались для написания нового. Тогда в префиксе самой строки Новый блок корректно закончит предыдущий блок (иначе бы массив <tex>z</tex> был бы некорректен, и предыдущий блок будет часть рассматриваемого префикса и часть нового префиксасовпадать с префиксом, то есть символы совпадут. Тогда тогда <tex>q[i] = z[i]</tex>.#Если блок лежит внутри другого блока, то его массив <tex>q</tex> совпадает с массивом для блока, содержащегося в префиксе строки. Проверяем корректность массива <tex>q</tex> для этого блока.
Таким образом, мы рассмотрели все случаи, при которых <tex>z[i] \ne 0</tex>, и показали корректность восстановления блока.
== См. также ==
* [[Префикс-функция]]
