275
правок
Изменения
→Описание
Рассмотрим сначала наивный метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.
=== Описание ===
{{Определение
|definition= '''Неявное суффиксное дерево''' строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления защитного символа.}}
[[Файл:ExampleUkkonen2.png|400px|thumb|right|Пример построения суффиксного дерева за <tex>O(n^3)</tex>.]]
Пусть строка <tex>S = s_1s_2...s_n</tex>. Построим неявное суффиксное дерево для <tex>s_1</tex>, после чего на каждой фазе алгоритма будем достраивать неявное суффиксное дерево подстроки <tex>s_1...s_{i-1}</tex> до неявного суффиксного дерева подстроки <tex>s_1...s_{i}</tex>. Обычное суффиксное дерево можно легко получить из неявного дерева для всей строки <tex>S</tex>.
== Возможные исходы операции insert ==
