275
правок
Изменения
→Суффиксные ссылки
Рассмотрим внутренную вершину <tex>v</tex> с путевой меткой <tex>t[i..j]</tex>. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>t[i+1..j]</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведет в <tex> u</tex>
}}
=== Использование суффиксных ссылок ===
[[Файл:ExampleUkkonen7.png|200px|thumb|right|Иллюстрация использования суффиксных ссылок.]]
Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корня. Пусть мы только что продлили суффикс <tex>s[l..i-1]</tex> до суффикса <tex>s[l..i]</tex> и стоим в вершине, в которую ведет ребро с пометкой <tex>t[k+1..r]</tex>, содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец суффикса <tex>s[l+1..i-1]</tex>. Пройдем вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведет ребро с пометкой <tex>t[p..k]</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует пометка <tex>t[h..k]</tex> (<tex>h</tex> и <tex>p</tex> могут быть не равны). Теперь пройдем от вершины <tex>u</tex> вниз по дереву к концу суффикса <tex>s[l+1..i-1]</tex>, и сделаем продление до суффикса <tex>s[l+1..i]</tex>.
=== Построение суффиксных ссылок ===
Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v </tex> с путевой меткой <tex>t[il..jr]</tex>. Не будем специально искать, куда должна указывать ссылка. Перейдем к следущему следующему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>ts[ij+1..ji]</tex> соответствующий вершине <tex>u</tex> (возможно до продления . Этот суффикс оканчивался может так же оканчиваться на ребре, но в этом случае по рассуждениям аналогичным [[#l1|Лемме 1]] тогда будет создана новая внутрення внутренняя вершина). По определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>. === Использование суффиксных ссылок === Опишем как искать концы суффиксов в дереве, которые нужно продлить. Пусть мы только что продлили суффикс <tex>t[i..j]</tex>. Найдем с помощью построенных ссылок конец суффикса <tex>t[i+1..j]</tex>. Пройдем вверх по дереву от конца суффикса <tex>t[i..j]</tex> до ближайшей внутренней определению суффиксная ссылка из вершины <tex>v</tex>. Ей соответствует некоторая подстрока <tex>t[i..k]</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует подстрока <tex>t[i+1..k]</tex>. Теперь пройдем от вершины <tex>u</tex> пройдем вниз по дереву, читая текст <tex>t[k+1..j]</tex>, и придем к концу суффикса <tex>t[i+1..j]</tex>.
==== Оценка числа переходов ====
Число переходов по ребрам внутри фазы номер <tex>i</tex> не превышает <tex>4i</tex>
|proof=
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по [[#l4|Лемме 4]]лемме, доказанной выше). Значит в течение одной фазы вверх мы переходим не более <tex> 2i </tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до <tex>1</tex>), поэтому вниз мы могли пройти не более <tex> 2i </tex> ребер. Итого получаем оценку <tex> 4i </tex>
}}
==Оптимизация алгоритма Укконена==
