Изменения

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