165
правок
Изменения
→Оценка сложности
== Оценка сложности ==
=== Память ===
{{Утверждение
|statement=
Каждая строка <tex>s</tex> содержит не более <tex>|s|</tex> подстрок-палиндромов.
|proof=
}}
Каждая вершина в дереве соответствует подпалиндрому, всего палиндромов в строке не более n.
Поэтому дерево палиндромов занимает <tex>O(n)</tex> памяти.
=== Время ===
Чтобы оценить временную сложность алгоритма, давайте посмотрим что происходит, когда мы строим дерево палиндромов. Можно заметить, что по мере того, как мы обрабатываем строку символ за символом, левая граница наибольшего палиндрома-суффикса уже обработанной строки сдвигается только вправо. Очевидно, эта граница может двигаться вправо не более <tex>n</tex>, где <tex>n</tex> {{---}} длина строки, для которой мы строим дерево. То же самое относится и к левой границе той строки, на которую ведет суффиксная ссылка вновь добавленной вершины.
Таким образом, суммарное время работы построения алгоритма <tex>O(n)</tex>.
== Применения ==
