Изменения

|statement=

При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>.

|proof=

Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>s[j..i]</tex> по суффиксной ссылке в вершину <tex> u </tex> с путевой меткой <tex>s[j+1..i]</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| \geqslant |B|</tex>, а значит <tex>d(u) \geqslant d(v) - 1</tex>