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> по суффиксным ссылкам.
