165
правок
Изменения
→Построение
|[[Файл:palindrome_tree_build3.png|500px|Цепочка суффиксных ссылок из t|border]]
|-
|Найдем теперь палиндром-суффикс нового префикса, состоящего из строки <tex>p</tex> и <tex>xpx</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|500px|border]]
