3622
правки
Изменения
→Построение строки по префикс-функции: некоторые мелкие правки
==Построение строки по префикс-функции==
===Постановка задачи===
Восстановить строку по префикс-функции за <tex>O(N)</tex> (, считая алфавит неограничен)неограниченным.
===Описание алгоритма===
Пусть в массиве <tex>p</tex> хранятся значения префикс-функции, в <tex>s</tex> будет записан ответ. Пойдем по массиву <tex>p</tex> слева направо.
Пусть мы хотим узнать значение <tex>s[i]</tex>. Для этого посмотрим на значение <tex>p[i]</tex>: если <tex>p[i] =0</tex> тогда в <tex>s[i]</tex> запишем новый символ, иначе <tex>s[i] ==Псевдокод===s[p[i]]</tex>. Обратим внимание, что <tex>s[p[i]]</tex> нам уже известно, так как <tex>p[i] < i</tex>. '''string''' buildFromPrefix('''int'''[] p) : s = "" '''for''' i = 0 '''to''' p.length - 1: '''if''' p[i] == 0 :
s += new char
s += s[p[i]]
===Доказательство корректности алгоритма===
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.
Пусть <tex>p</tex> данная префикс-функция, <tex>s'</tex> правильная строка, строку <tex>s</tex> эту строку построил наш алгоритм, <tex> q </tex> массив значений префикс-функции для <tex>s</tex>.
Докажем корректность индукцией по длине массива префикс-функции полученной строки.
* База очевидна для строки длиной <tex>1</tex>.
* Переход: Пусть пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[1..n - 1] = q[1..n - 1]</tex>. Возможно Возможны два варианта,случая:
<tex>1)</tex> <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>. Также, предыдущие значения <tex>q</tex> не поменяются и останутся верными.
