275
правок
Изменения
м
→Суффиксные ссылки
{{Определение
|definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, где <tex>x</tex> {{---}} ее первый символ, а <tex>\alpha</tex> {{---}} оставшаяся подстрока (возможно пустая). Если для внутренней вершины <tex>v</tex> с путевой меткой <tex>x\alpha</tex> существует другая вершина <tex>s(v)</tex> с путевой меткой <tex>\alpha</tex>, то ссылка из <tex>v</tex> в <tex>s(v)</tex> называется '''суффиксной ссылкой''' (англ. ''suffix link'').}}
{{Лемма|id=l3
|about= Существование суффиксных ссылок
=== Использование суффиксных ссылок ===
[[Файл:ExampleUkkonen7ExampleUkkonen8.png|200px|thumb|right|Иллюстрация использования суффиксных ссылокПример суффиксной ссылки.]]
Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корня. Пусть мы только что продлили суффикс <tex>s[j..i-1]</tex> до суффикса <tex>s[j..i]</tex> и стоим в вершине, в которую ведет ребро с пометкой <tex>t[k+1..r]</tex>, содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец суффикса <tex>s[j+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[j+1..i-1]</tex>, и сделаем продление до суффикса <tex>s[j+1..i]</tex>.
