Изменения
Нет описания правки
|definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, где <tex>x</tex> {{---}} ее первый символ, а <tex>\alpha</tex> {{---}} оставшаяся подстрока(возможно пустая). Если для внутренней вершины с путевой меткой <tex>x\alpha</tex> существует другая вершина <tex>s(v)</tex> с путевой меткой <tex>\alpha</tex> то ссылка из <tex>v</tex> в <tex>s(v)</tex> называется суффиксной ссылкой.}}
===Лемма 13. Существование суффиксных ссылок ===
{{Лемма
|statement=
|definition= <b>Глубиной вершины</b> <tex>d(v)</tex> назовем число ребер на пути от корня до вершины <tex>v</tex>}}
===== Лемма 4. ====
{{Лемма
|statement=
}}
===== Лемма 5. ====
{{Лемма
|statement=
Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> (по Лемме 1)
По Лемме 2 алгоритм делает не более <tex>2*n2n</tex> явных продлений. При использовании суффиксных ссылок, как показано в Лемме X 5 время на продление равно константе плюс время пропорциональное числу ребер, пройденных при спуске по дереву. Оценим суммарное число таких переходов по ребрам. Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в лемме XЛемме 5, каждое продление представляет собой переход не более чем на 2 единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на 1. Так как максимальная глубина не превосходит <tex>n</tex>, а колличество явных продлений не превышает <tex>2*n2n</tex>, то по рассуждениям аналогичным Лемме X 5 суммарное число таких переходов имеет порядок <tex>O(n)</tex>
