165
правок
Изменения
→Построение
== Построение ==
Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс <tex>p</tex> и теперь хотим добавить следующий символ строки, назовем его <tex>x</tex>.
[[Файл:palindrome_tree_build1.png|border]]
Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>.
[[Файл:palindrome_tree_nodes.png|border]]
Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д.
[[Файл:palindrome_tree_build3.png|Цепочка суффиксных ссылок из t|border]]
== Реализация ==
