Изменения
Нет описания правки
Оценим колличество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на 1. Переход по суффиксной ссылке уменьшает высоту не более чем на 1 (по Лемме). Значит в течение одной фазы вверх мы переходим не более <tex> 2i </tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до 1), поэтому вниз мы могли пройти не более <tex> 2i </tex> ребер. Итого получаем оценку <tex> 4i </tex>
}}
== Итоговая линейная оценка ==
Оценим время работы алгоритма при использовании всех вышеперечисленных эвристик.
Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> (по Лемме 1)
По Лемме 2 алгоритм делает не более <tex>2*n</tex> явных продлений. При использовании суффиксных ссылок, как показано в Лемме X время на продление равно константе плюс время пропорциональное числу ребер, пройденных при спуске по дереву. Оценим суммарное число таких переходов по ребрам. Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в лемме X, каждое продление представляет собой переход не более чем на 2 единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на 1. Так как максимальная глубина не превосходит <tex>n</tex>, а колличество явных продлений не превышает <tex>2*n</tex>, то по рассуждениям аналогичным Лемме X суммарное число таких переходов имеет порядок <tex>O(n)</tex>
== Источник ==
