Изменения

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

Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v </tex> с путевой меткой <tex>t_i t[i... t_jj]</tex>. Перейдем к следущему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>t_{t[i + 1} ... t_jj]</tex> соответствующий вершине <tex>u</tex> (возможно до продления суффикс оканчивался на ребре, но в этом случае по рассуждениям аналогичным [[#l1|Лемме 1]] будет создана новая внутрення вершина). По определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>.

Опишем как искать концы суффиксов в дереве, которые нужно продлить. Пусть мы только что продлили суффикс <tex>t_i t[i... t_jj]</tex>. Найдем с помощью построенных ссылок конец суффикса <tex>t_{t[i + 1} ... t_jj]</tex>. Пройдем вверх по дереву от конца суффикса <tex>t_i t[i... t_jj]</tex> до ближайшей внутренней вершины <tex>v</tex>. Ей соответствует некоторая подстрока <tex>t_i t[i... t_k k]</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует подстрока <tex>t_{t[i + 1} ... t_kk]</tex>. Теперь пройдем от вершины <tex>u</tex> пройдем вниз по дереву, читая текст <tex>t_{t[k + 1} ... t_jj]</tex>, и придем к концу суффикса <tex>t_{t[i + 1} ... t_jj]</tex>.

Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>t_i t[i... t_jj]</tex> по суффиксной ссылке в вершину <tex> u </tex> с путевой меткой <tex>t_{t[i + 1} ... t_jj]</tex> Определим множество <tex> A </tex> как множество вершин на пути от корня до <tex> u </tex>, исключая корень. Множество <tex> B </tex> определим как множество вершин на пути от корня до <tex> v </tex>, исключая корень. Если длина первого ребра на пути от корня до <tex> v </tex> равна единице, то выкинем из множества <tex>B</tex> вершину, в которую ведет это ребро. Итого по построению получаем: <tex>|A| = d(u)</tex>, <tex>|B| \ge d(v) - 1</tex>. Теперь заметим, что суффиксная ссылка из любой вершины множества <tex>B</tex> ведет в некоторую вершину множества <tex> A</tex>, и очевидно суффиксные ссылки из разных вершин ведут в разные вершины, поэтому <tex>|A| \ge |B|</tex>, а значит <tex>d(u) \ge d(v) - 1</tex>