80
правок
Изменения
→Построение суффиксного дерева
==Построение суффиксного дерева==
Рассмотрим наивный алгоритм построения суффиксного дерева.: '''for''' <tex> i \leftarrow 0 </tex> '''to''' <tex> n </tex> '''do''' //для каждого символа строки insert(<tex>i, n</tex>) //добавляем суффикс, начинающийся с негоЭтот алгоритм работает за время<tex>O(n^2)</tex>, однако существует [[Алгоритм Укконена| алгоритм Укконена]], позволяющий построить дерево за время<tex>O(n)</tex>.
==Использование==