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