Изменения

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