275
правок
Изменения
→Использование суффиксных ссылок
=== Использование суффиксных ссылок ===
[[Файл:ExampleUkkonen7.png|300px|thumb|right|Использование суффиксных ссылок.]]
Сейчас на каждой итерации алгоритм выполняет <tex>O(n^2)</tex> действий, так как до конца каждого суффикса мы спускаемся из корня. ЗаметимОчевидно, что быстрее было бы спуститься от корня только один раз, до конца суффикса, который мы продлеваем первым на текущем шаге, а потом каким-то способом переходить от конца одного суффикса к концу другого следующего суффикса за <tex>O(1)</tex>. Суффиксные ссылки используются как раз для того, чтобы делать подобные переходы.
Рассмотрим один такой переход, пусть мы только что продлили суффикс <tex>s[j..i-1]</tex> до суффикса <tex>s[j..i]</tex>. Теперь с помощью построенных ссылок найдем конец суффикса <tex>s[j+1..i-1]</tex>, чтобы продлить его до суффикса <tex>s[j+1..i]</tex>. Пройдем вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведет путь, помеченный <tex>s[j..r]</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для внутренней вершины строится внутри фазы создания этой вершины. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует путь с пометкой <tex>s[j+1..r]</tex>. Теперь пройдем от вершины <tex>u</tex> вниз по дереву к концу суффикса <tex>s[j+1..i-1]</tex>, и сделаем продление до суффикса <tex>s[j+1..i]</tex>.
=== Построение суффиксных ссылок ===
