Изменения

Рассмотрим один такой переход, пусть мы применение суффиксных ссылок. Пусть только что продлили был продлён суффикс <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>.

Концы суффиксов Можно заметить, что подстрока <tex>s[j+1..i-1]</tex> и является суффиксом подстроки <tex>s[j+1..i-1]</tex> совпадают. Следовательно, следовательнопосле перехода по суффиксной ссылке в вершину, зная сколько символов мы просмотрели на метке содержащей конец помеченную путевой меткой <tex>s[j+1..i-1r]</tex> суффикса, можно сразу перейти к проверке существования перехода по символу <tex>s_i</tex> для суффикса дойти до места, которму соответствует метка <tex>s[jr+1..i-1]</tex>, сравнивая не символы на рёбрах, а лишь длину ребра по первому символу рассматриваемой части подстроки и длину самой этой подстроки. Таким образом можно спускаться вниз сразу на целое ребро.