275
правок
Изменения
Нет описания правки
Благодаря суффиксным ссылкам количество действий на одной итерации снижается с <tex>O(n^2)</tex> до <tex>O(n)</tex>, так как по доказанной выше лемме на каждом шаге мы делаем не более O(n) переходов. Следовательно, общая асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.
==Оптимизация алгоритма Укконена до O(n)Линейный алгоритм==
{{Лемма|id=l1
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>j+1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении i, то уже не требуется явно находить концы строк <tex>s[k..j]</tex> с <tex>k > i</tex>.
Рассмотрим правила продолжения суффиксов.
* При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. <br>
* При использовании правила 3 по [[#l2|лемме 2]] никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.
=== Итоговая оценка времени работы ===
Оценим время работы алгоритма при использовании всех вышеперечисленных эвристик.
Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> ([[#l1|по Лемме 1]])
[[#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>
== Псевдокод ==
tree_extend (i)
</code>
== См. также==
