Изменения

Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по лемме, доказанной выше). Значит в течение одной фазы вверх мы переходим не более <tex>2i</tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до <tex>1</tex>), поэтому вниз мы могли пройти не более <tex>2i</tex> ребер. Итого получаем оценку <tex>4i</tex>.