Изменения

Перейти к: навигация, поиск

Алгоритм Укконена

30 байт убрано, 21:52, 10 апреля 2015
Первая версия алгоритма
'''Алгоритм Укконена''' (англ. ''Ukkonen's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время.
== Первая версия алгоритма Алгоритм за <tex>O(n^3)</tex> ==
Рассмотрим сначала наивный метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.
=== Описание ===
{{Определение
|definition= '''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления защитного символа.}}
275
правок

Навигация