Изменения

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

== См. также==