146
правок
Изменения
→Построение строки по Z-функции
|definition= Необходимо восстановить строку по Z-функции, считая алфавит ограниченным.
}}
===Описание алгоритма===
Пусть в массиве <tex>z</tex> хранятся значения Z-функции, в <tex>s</tex> будет записан ответ. Пойдем по массиву <tex>z</tex> слева направо.
Пусть <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>q[i]</tex>. Тогда массив <tex>q</tex> совпадает с <tex>z</tex> был некорректный. Значит, мы не изменяем префикс, когда пишем другой префикс, пересекающийся с ним, поэтому с помощью этого алгоритма мы получим строку с Z-функцией, совпадающей с заданной.
Покажем, что этот алгоритм эквивалентен нашему алгоритму. Когда мы пишем разные префиксы, то возможны три варианта: они не пересекаются, один лежит внутри другого, они пересекаются.
* Если префиксы не пересекаются, то в алгоритме они не влияют друг на друга.
* Если префикс лежит внутри другого префикса, то записав большой префикс мы запишем и малый.
* Если префиксы пересекаются, то нам нужно переписать часть первого префикса , который начинается раньше, и полностью второй начать писать другой префикс.
Таким образом, алгоритмы эквивалентны и наш алгоритм тоже корректен.
