Изменения
Нет описания правки
Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v </tex> с путевой меткой <tex>t_i ... t_j</tex>. Перейдем к следущему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>t_{i + 1} ... t_j</tex> соответствующий вершине <tex>u</tex> (возможно до продления суффикс оканчивался на ребре, но в этом случае по рассуждениям аналогичным Лемме 1 будет создана новая внутрення вершина). По определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>.
=== Использование суффиксных ссылок ===
Опишем как искать концы суффиксов в дереве, которые нужно продлить. Пусть мы только что продлили суффикс <tex>t_i ... t_j</tex>. Найдем с помощью построенных ссылок конец суффикса <tex>t_{i + 1} ... t_j</tex>. Пройдем вверх по дереву от конца суффикса <tex>t_i ... t_j</tex> до ближайшей внутренней вершины <tex>v</tex>. Ей соответствует некоторая подстрока <tex>t_i ... t_k </tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует подстрока <tex>t_{i + 1} ... t_k</tex>. Теперь пройдем от вершины <tex>u</tex> пройдем вниз по дереву, читая текст <tex>t_{k + 1} ... t_j</tex>, и придем к концу суффикса <tex>t_{i + 1} ... t_j</tex>.
==== Оценка числа переходов ====
== Источник ==
