165
правок
Изменения
→Построение
{{Утверждение
|author=1
|statement=
Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>px</tex>, которой, возможно, нет в <tex>p</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> по суффиксным ссылкам.
Заметим также, что очередная добавленная вершина <tex>u</tex> не может быть максимальным палиндромом-суффиксом какой-либо ранее добавленной вершины <tex>v</tex>, т.к. это означало бы, что не все подпалиндромы строки <tex>v'</tex> были добавлены в дерево палиндромов. А это противоречит утверждению 1.
== Оценка сложности ==
