Изменения
Нет описания правки
Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в [[#l5|Лемме 5]], каждое продление представляет собой переход не более чем на <tex>2</tex> единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на <tex>1</tex>. Так как максимальная глубина не превосходит <tex>n</tex>, а количество явных продлений не превышает <tex>2n</tex>, то по рассуждениям аналогичным [[#l5|Лемме 5]] суммарное число таких переходов имеет порядок <tex>O(n)</tex>
== См. также==
* [[Алгоритм Фарача]]
== Источники ==
* Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена]
* [http://habrahabr.ru/post/111675/ Habrahabr - Построение суффиксного дерева: алгоритм Укконена]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Словарные структуры данных]]
[[Категория: Суффиксное дерево]]
