275
правок
Изменения
→Описание
|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>\tau_1</tex> для <tex>s_1</tex>, после чего на каждой фазе алгоритма будем достраивать неявное суффиксное дерево <tex>\tau_{i-1}</tex> подстроки <tex>s_1...s_{i-1}</tex> до неявного суффиксного дерева <tex>\tau_i</tex> подстроки <tex>s_1...s_{i}</tex>. Обычное суффиксное дерево можно легко получить из неявного дерева для всей строки <tex>S\tau_n</tex>, достроив его до <tex>\tau_{n+1}</tex>, где <tex>s_{n+1}=\$</tex>.
== Возможные исходы операции insert ==
