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> по суффиксным ссылкам.
Строка <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>.
Таким образом, чтобы обработать очередной символ <tex>x</tex>, нужно просто спуститься по суффиксным ссылкам строки <tex>t</tex> до тех пор, пока мы не найдем подходящую строку <tex>A</tex> (причем мы всегда можем найти такую строку, возможно длины <tex>-1</tex>, если очередная суффиксная ссылка будет вести в корень). Затем нужно проверить, есть ли уже ребро по символу <tex>x</tex> из вершины, соответствующей <tex>A</tex>, и если нет, добавить это ребро в новую вершину <tex>xAx</tex>.
Теперь нужно добавить суффиксную ссылку из вершины <tex>xAx</tex>. Если эта вершина уже существовала до добавления символа <tex>x</tex>, ничего делать не нужно {{---}} суффиксная ссылка итак указывает на правильную вершину. Иначе на нужно найти наибольший палиндром-суффикс строки <tex>xAx</tex>, который будет иметь вид <tex>xBx</tex>, где <tex>B</tex> {{---}} это некоторая строка, возможно, пустая. Следуя той же логике, которую мы использовали раньше, <tex>B</tex> {{---}} это палиндром-суффикс строки <tex>p</tex> и может быть достигнут из <tex>t</tex> по суффиксным ссылкам.
