Изменения

Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корня. Пусть мы только что продлили суффикс <tex>s[lj..ri-1]</tex> до суффикса <tex>s[lj..ri]</tex> и стоим в вершине, в которую ведет ребро с пометкой <tex>t[k+1..ir]</tex>, содержащей конец текущего суффикса. Найдем с помощью построенных ссылок конец суффикса <tex>s[lj+1..ri-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[lj+1..ri-1]</tex>, и сделаем продление до суффикса <tex>s[lj+1..ri]</tex>.