Изменения

|definition= Восстановить Необходимо восстановить строку по Z-функции за <tex>O(n)</tex>, считая алфавит ограниченным.

Алгоритм Заметим, что не всегда сможет построить удастся восстановить строку по корректному массиву значений с ограниченным алфавитом неподходящего размера. Например, для строки <tex>abacaba</tex> массив Z-функций будет <tex>[0, 0, 1, 0, 3, 0, 1]</tex>. Используя двоичный алфавит, мы получим строку <tex>abababa</tex>, но её массив Z-функциифункций отличается от исходного. Ошибка восстановления строки возникла, если в алфавите больше одного символакогда закончились новые символы алфавита.

Если строить строку по некорректному массиву значений Z-функции, то мы получим какую-то строку, но массив значений Z-функций от неё будет отличаться от исходного.

Пусть <tex>z</tex> — данная Z-функция, строку <tex>s</tex> построил наш алгоритм, <tex>q</tex> — массив значений Z-функции для <tex>s</tex>. Покажем, что массивы <tex>q</tex> и <tex>z</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>z</tex> был некорректный. Значит, мы не изменяем префикс, когда пишем другой префикс, пересекающийся с ним, поэтому с помощью этого алгоритма мы получим строку с Z-функцией, совпадающей с заданной.

Если <tex>z[i] = 0</tex>Покажем, то по что этот алгоритм эквивалентен нашему алгоритму <tex>s[i]</tex> будет отличаться от <tex>s[0]</tex>. ТогдаКогда мы пишем разные префиксы, при подсчёте Z-функции для полученной строкито возможны три варианта: они не пересекаются, мы получимодин лежит внутри другого, что <tex>q[i] = 0</tex>они пересекаются.* Если префиксы не пересекаются, ведь <tex>s[i] \neq s[0]</tex>то они не влияют друг на друга. Значит* Если префикс лежит внутри другого префикса, если <tex>z[i] = 0</tex>то записав большой префикс мы запишем и малый.* Если префиксы пересекаются, то <tex>z[i] = q[i]</tex>нам нужно переписать часть первого префикса и полностью второй префикс.

Рассмотрим значения <tex>z[i] \ne 0</tex>. В этом случае <tex>s[i]</tex> является началом префикса исходной строки. Будем называть подстроки, совпадающие с префиксом строки, блоками. Возможны три случая:* Мы полностью записали рассматриваемый блок длиной <tex>z[i]</tex>. По определению Z-функции <tex>q[i] = z[i]</tex>.* Мы записали часть рассматриваемого блока <tex>b_1</tex> и прервались, чтобы записать новый блок <tex>b_2</tex>. Допустим, что мы полностью написали блок <tex>b_1</tex>, а после написали блок <tex>b_2</tex>. В таком случае мы переписали символы в пересечении двух блоков. Эти символы совпадают, иначе массив <tex>z</tex> был бы некорректным. Поэтому блок <tex>b_1</tex> запишется правильно и полностью. Этот случай мы уже рассмотрели выше.* Рассматриваемый блок <tex>b_1</tex> полностью покрывается блоком <tex>b_2</tex>, который мы уже пишем. Допустим, что мы напишем блок <tex>b_1</tex> после того, как написали блок <tex>b_2</tex>. При корректном массиве <tex>z</tex> символы в пересечении двух блоков совпадут. Тогда мы можем просто рассматривать блок <tex>b_1</tex> аналогично одному из предыдущих случаев. Таким образом, мы доказали, что значения массивов <tex>q</tex> алгоритмы эквивалентны и <tex>z</tex> совпадаютнаш алгоритм тоже корректен.