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>. <tex>s[p[i]]</tex> мы посчитали раньше(<tex>p[i]<=i</tex>). Так как подстрока с 1 по <tex>p[i]</tex> заканчивается в <tex>s[i]</tex> то <tex>s[i]</tex> должен быть равен <tex>s[p[i]]</tex>
===Псевдокод===
string s;
