==Построение строки по префикс-функции==
Формулировка ===Постановка задачи восстановить === Восстановить строку по префикс-функции за <tex>O</tex>(<tex>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>
== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.
