165
правок
Изменения
→Применения
== Применения ==
=== Как много новых палиндромов появляется при добавлении нового символа ===
В данной задаче нужно уметь отвечать на вопрос <tex>``</tex>как много новых палиндромов-подстрок появится у строки <tex>s</tex>, если к ней в конец добавить символ <tex>x"</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>. Так что решение задачи довольно простое - будем строить дерево палиндромов символ за символом и для каждого нового символа отвечать, был ли добавлен новый палиндром или нет (определить это можно, например, по тому, были ли добавлены новые вершины к структуре).
=== Количество подпалиндромов ===
В данной задаче нужно уметь отвечать на вопрос <tex>``</tex> как много подпалиндромов имеет данная строка <tex>"</tex>. Например, строка <tex>aba</tex> имеет четыре подпалиндрома: дважды <tex>a</tex>, <tex>b</tex> и <tex>aba</tex>.
Для решения задачи построим дерево палиндромов для данной строки. При обработке очередного символа добавим к ответу все палиндромы, которые содержат этот новый символ. Заметим, что эти палиндромы {{---}} это новый максимальный палиндром-суффикс <tex>t</tex>, который содержит новый символ, и все полиндромы, достижимые из <tex>t</tex> по суффиксным ссылкам. Для того чтобы быстро найти их количество будем хранить в каждой вершине дерева палиндромов длину цепочки суффиксных ссылок (включая саму вершину), а затем будем просто прибавлять к ответу это число для каждого <tex>t</tex> по мере добавления новых символов.
Эта задача также может быть решена [[Алгоритм_Манакера|алгоритмом Манакера]] за ту же асимптотику, однако данный алгоритм не может быть расширен для более широкого класса задач, в отличие от дерева палиндромов.
=== Количество вхождений каждого подпалиндрома в строку ===
В этой задаче необходимо найти количество вхождений каждого подпалиндрома строки.
Чтобы решить эту задачу деревом палиндромов, нужно обратить внимание на то, что при добавлении нового символа увеличивается количество вхождений наибольшего палиндрома-суффикса <tex>t</tex>, содержащего новый символ, и всех палиндромов, достижимых из <tex>t</tex> по суффиксным ссылкам.
Для каждой вершины <tex>u</tex> дерева палиндромов будем хранить число <tex>u.num</tex> {{---}} количество вхождений соответствующего вершине палиндрома в исходную строку (не обязательно актуальные данные) и число <tex>u.toAdd</tex>, которое необходимо добавить к <tex>v.num</tex> всех потомков <tex>v</tex> вершины <tex>u</tex>. Назовем такую операцию '''операцией релаксации'''. После того, как релаксация будет выполнена для всех предков вершины <tex>u</tex>, можно будет считать, что <tex>u.num</tex> содержит актуальные данные.
Данный метод очень похож на метод, описанный в статье [[Несогласованные_поддеревья._Реализация_массового_обновления|про реализацию массовых обновлений в деревьях отрезков]].
== Источники ==
