165
правок
Изменения
→Применения
Для каждой вершины <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> содержит актуальные данные.
Данный метод очень похож на метод, описанный в статье [[Несогласованные_поддеревья._Реализация_массового_обновления|про реализацию массовых обновлений в деревьях отрезков]].
=== Поиск рефрен-палиндрома ===
Для данной строки необходимо найти палиндром, произведение длины которого на количество вхождений в строку является максимальным.
Для решения данной задачи применим тот же алгоритм, что и в прошлой задаче, затем пройдем по всем вершинам дерева палиндромов и выберем подходящую.
== Источники ==
