Построение суффиксного дерева в RAM: различия между версиями

Временная сложность построения суффиксного дерева для строки S длины n зависит от размера базового алфавита <math>\Sigma \;</math>. Он может быть константным, может быть целочисленным <math>\Sigma = \{1, 2, ., n \} \;</math>, а может быть произвольным конечным множеством, элементы которого можно сравнивать за константное время. Заметим, что третий случай можно свести ко второму, если отобразить символы алфавита на множество {1, ..., n}, хотя при этом возникают дополнительные затраты на сортировку <math>\Sigma \;</math>.

Если предположить, что ребра, выходящие из каждой вершины, лексикографически упорядочены, что обычно имеет место, суффиксное дерево позволяет получить отсортированный порядок S' символов за линейное время. Таким образом, построение суффиксного дерева наследует нижние границы сложности задачи сортировки: <math>\Omega(n \; log \; n)</math> в случае алфавита общего вида и <math>\Omega(n) \;</math> для целочисленных алфавитов.