Изменения

== Применения ==

=== Число новых палиндромов, порождаемых очередным символом ===

Например, при добавлении символа <tex>a</tex> к строке <tex>aba</tex>, которая уже состоит из палиндромов <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>, добавляется новый палиндром <tex>aa</tex>.

=== Число подпалиндромов ===

Для решения задачи построим дерево палиндромов для данной строки. При обработке очередного символа добавим к ответу все палиндромы, которые содержат этот новый символ. Заметим, что эти палиндромы {{---}} это новый максимальный палиндром-суффикс <tex>t</tex>, который содержит новый символ, и все полиндромы, достижимые из <tex>t</tex> по суффиксным ссылкам. Для того чтобы быстро найти их количество будем хранить в каждой вершине дерева палиндромов длину цепочки суффиксных ссылок (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого <tex>t</tex> по мере добавления новых символов.

=== Число вхождений каждого подпалиндрома в строку ===

Чтобы решить эту задачу деревом палиндромов, нужно обратить внимание на то, что при добавлении нового символа увеличивается количество вхождений наибольшего палиндрома-суффикса <tex>t</tex>, содержащего новый символ, и всех палиндромов, достижимых из <tex>t</tex> по суффиксным ссылкам.

=== Поиск рефрен-палиндрома ===

Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.