Изменения

Рассмотрим внутренную вершину <tex>v</tex> с путевой меткой <tex>ts[i..j]</tex>. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>ts[i+1..j]</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведет в <tex> u</tex>

Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корня. Пусть мы только что продлили суффикс <tex>s[j..i-1]</tex> до суффикса <tex>s[j..i]</tex> и стоим в вершине, в которую ведет ребро . Теперь с пометкой помощью построенных ссылок найдем конец суффикса <tex>ts[kj+1..ri-1]</tex>, содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец чтобы продлить его до суффикса <tex>s[j+1..i-1]</tex>. Пройдем вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведет ребро с пометкой <tex>ts[pr..kl]</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее созданияэтой вершины. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует пометка ребро с пометкой <tex>ts[h..kl]</tex> (<tex>h</tex> и <tex>pr</tex> могут быть не равны). Теперь пройдем от вершины <tex>u</tex> вниз по дереву к концу суффикса <tex>s[j+1..i-1]</tex>, и сделаем продление до суффикса <tex>s[j+1..i]</tex>.

Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v</tex> с путевой меткой <tex>ts[l..r]</tex>. Не будем специально искать, куда должна указывать ссылка. Перейдем к следующему шагу текущей фазы, на котором в дерево суффикс <tex>s[j+1..i-1]</tex> будет добавлен суффикс увеличен до суффикса <tex>s[j+1..i]</tex>. Этот суффикс может так же оканчиваться на ребре, но тогда будет создана новая внутренняя вершина <tex>u</tex>, по в которую определению и будет вести суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>.