Изменения

{{Лемма|id=l4

|statement=

|proof=

Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>t_i ... t_j</tex> по суффиксной ссылке в вершину <tex> u </tex> с путевой меткой <tex>t_{i + 1} ... t_j</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>