275
правок
Изменения
→Суффиксные ссылки
Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v</tex> с путевой меткой <tex>t[l..r]</tex>. Не будем специально искать, куда должна указывать ссылка. Перейдем к следующему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>s[j+1..i]</tex>. Этот суффикс может так же оканчиваться на ребре, но тогда будет создана новая внутренняя вершина <tex>u</tex>, по определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>.
{{Определение
Число переходов по ребрам внутри фазы номер <tex>i</tex> не превышает <tex>4i</tex>
|proof=
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по лемме, доказанной выше). Значит в течение одной фазы вверх мы переходим не более <tex> 2i </tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до <tex>1</tex>), поэтому вниз мы могли пройти не более <tex> 2i </tex> ребер. Итого получаем оценку <tex> 4i </tex>
}}
=== Асимтотика алгоритма с использованием суффиксных ссылок ===
Благодаря суффиксным ссылкам количество действий на одной итерации снижается с <tex>O(n^2)</tex> до <tex>O(n)</tex>, так как по доказанной выше лемме на каждом шаге мы делаем не более O(n) переходов. Следовательно, общая асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.
==Оптимизация алгоритма Укконена==
