275
правок
Изменения
Нет описания правки
Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> ([[#l1|по Лемме 1]]). [[#l2|По Лемме 2]] алгоритм делает не более <tex>2n</tex> явных продлений. Таким образом, в течение всех <tex>n</tex> итерация суммарно выполняется не более <tex>O(n)</tex> продлений, следовательно, с использованием всех приведенных эвристик, алгоритм Укконена работает за <tex>O(n)</tex>.
== Минусы алгоритма Укконена ==
Не смотря на то, что данный алгоритм является одном из самых простых алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьезные недостатки, из-за которых его не часто используют на практике.
== Реализация ==
