165
правок
Изменения
→Построение
[[Файл: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> по суффиксным ссылкам.
