Изменения

В любой фазе, если правило продолжения продления 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>i+1</tex> по <tex>j+1</tex>) до конца фазы.

Когда используется 3-е правило 3продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>j+1</tex> текущую итерацию после первого же использования этого правила прохождения 3. Если это случится Так как лист навсегда останется листом, зададим метку ребра ведущего в продолжении i, то уже не требуется явно находить концы строк этот лист как <tex>st[ki..jx]</tex> с , где <tex>k x</tex>{{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex> i</tex>. Рассмотрим правила продолжения суффиксов. * При использовании правила 1 по [[#l1|лемме 1]] в последующих фазах будет выполняться правило 1. Поэтому скажем, что Таким образом мы создаём лист не только для рассмотренной части строкисможем удлинять все суффиксы, а для всей всей строки до конца. заканчивающиеся в листах за <brtex>* При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу O(1. )<br/tex>* При использовании правила 3 по [[#l2|лемме 2]] никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.

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

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