165
правок
Изменения
→Число новых палиндромов, порождаемых очередным символом
Например, при добавлении символа <tex>a</tex> к строке <tex>aba</tex>, которая уже состоит из палиндромов <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>, добавляется новый палиндром <tex>aa</tex>.
Мы знаем, что число новых подпалиндромов при добавлении символа - это <tex>0</tex> или <tex>1</tex>. Так что решение задачи довольно простое - будем строить дерево палиндромов символ за символом и для каждого нового символа отвечать, был ли добавлен новый палиндром или нет (определить это можно, например, по тому, были ли добавлены новые вершины к структуре).
=== Число подпалиндромов ===
