165
правок
Изменения
→Построение
[[Файл:palindrome_tree_build3.png|Цепочка суффиксных ссылок из t|border]]
Найдем теперь палиндром-суффикс нового префикса, состоящего из <tex>p</tex> и <tex>x</tex>. Искомый палиндром-суффикс будет иметь вид <tex>``xAx"</tex>, где <tex>A</tex> {{---}} это какая-то строка, возможно пустая (или фиктивный строка длины -1, соответствующая корню <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>.
So, to process new letter x we just go along suffix links of t until we find an appropriate A (and we always find some, possibly of length -1 if we trace suffix links back to the roots). Then we check if there is an edge on letter x from the node corresponding to A, and if not, set this edge going to the new node corresponding to xAx.
What about suffix link of the node xAx? If this node already existed before, the suffix link was also already set and we don't need to do anything. If not, then we need to find the largest suffix-palindrome of xAx, which will be in a form of xBx, where B is some string, possibly empty. By the same logic that we used before, B is a suffix-palindrome of p and can be reached from t by suffix links.
== Реализация ==
