Заметим также, что очередная {{Утверждение|statement=Очередная добавленная вершина <tex>u</tex> не может быть максимальным палиндромом-суффиксом какой-либо ранее добавленной вершины <tex>v</tex>|proof=Предположим, т.кчто это не так. это означало быТогда оказывается, что не все подпалиндромы строки <tex>v'</tex> были добавлены в дерево палиндромовранее. А это противоречит утверждению 1.}} Таким образом, добавление очередного символа по описанному алгоритму происходит корректно.
== Оценка сложности ==
