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