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