165
правок
Изменения
→Построение
== Построение ==
{| border="1" |- |Будем обрабатывать строку символ за символом. Пусть мы уже обработали некоторый префикс <tex>p</tex> и теперь хотим добавить следующий символ строки, назовем его <tex>x</tex>. |[[Файл:palindrome_tree_build1.png|border]] |- |Будем также поддерживать максимальный палиндром-суффикс обработанного префикса <tex>p</tex>. Назовем его <tex>t</tex>. |[[Файл:palindromic_tree_nodes.png|border]] |- |Т.к. <tex>t</tex> находится в уже обработанной части строки, то ему соответствует какая-то вершина в дереве. У этой вершины есть суффиксная ссылка на какую-то другую вершину, у которой тоже есть суффиксная ссылка и т.д. |[[Файл:palindrome_tree_build3.png|Цепочка суффиксных ссылок из t|border]] |- |Найдем теперь палиндром-суффикс нового префикса, состоящего из <tex>p</tex> и <tex>x</tex>. Искомый палиндром-суффикс будет иметь вид <tex>xAx</tex>, где <tex>A</tex> {{---}} какая-то строка, возможно пустая (или фиктивный строка длины <tex>-1</tex>, соответствующая корню <tex>root_{odd}</tex>, если искомый палиндром-суффикс {{---}} это просто символ <tex>x</tex>).
Т.к. <tex>xAx</tex> палиндром, то <tex>A</tex> {{---}} тоже палиндром, и, более того, это суффикс строки <tex>p</tex>. Поэтому он может быть достигнут из <tex>t</tex> по суффиксным ссылкам.
|[[Файл:palindrome_tree_build4.png|border]] |}
Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>p+x</tex>, которой, возможно, нет в <tex>p</tex> (все другие подстроки-палиндромы есть). Чтобы понять почему это так, нужно обратить внимание на то, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>p+x</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>p+x</tex>, все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки <tex>xAx</tex> (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в <tex>p</tex>.
