668
правок
Изменения
→Построение строки по префикс-функции
===Описание алгоритма===
Пусть в массиве <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>. Так как подстрока с 1 по <tex>p[i]</tex> заканчивается в <tex>s[i]</tex> то <tex>s[i]</tex> должен быть равен <tex>s[p[i]]</tex>===Псевдокод=== string s; vector<int> p; for (int i = 0; i < p.size(); i++) { if (p[i] == 0) { s += new char; } else { s += s[p[i]]; } }
== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.
