Изменения
Нет описания правки
{{Определение
|definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, где <tex>x</tex> {{---}} ее первый символ, а <tex>\alpha</tex> {{---}} оставшаяся подстрока(возможно пустая). Если для внутренней вершины с путевой меткой <tex>x\alpha</tex> существует другая вершина <tex>s(v)</tex> с путевой меткой <tex>\alpha</tex> то ссылка из <tex>v</tex> в <tex>s(v)</tex> называется суффиксной ссылкой.}}
===Лемма 1. Существование суффиксных ссылок ===
{{Лемма
|statement=
Для любой внутренней вершины суффиксного дерева, существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину.
|proof=
Рассмотрим внутренную вершину <tex>v</tex> с путевой меткой <tex>t1_ ... t_k</tex>. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>t2_ ... t_k</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v</tex> ведет в <tex> u</tex>
}}
== Источник ==
