3622
правки
Изменения
→Описание алгоритма
Пусть в массиве <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>.
=== Реализация ===
