Изменения
→Суффиксные ссылки
==== Оценка числа переходов ====
{{Определение
|definition= <b>Глубиной вершины</b> <tex>d(v)</tex> назовем число ребер на пути от корня до вершины <tex>v</tex>}}
{{Лемма
|statement=
При переходе по суффиксной ссылке глубина уменьшается не более чем на 1.
|proof=
Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>t_i ... t_j</tex> по суффиксной ссылке в вершину <tex> u </tex> с путевой меткой <tex>t_{i + 1} ... tj</tex>
}}
== Источник ==
