Изменения

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