Изменения

Теперь в начале каждой фазы мы только один раз спускаемся от корня, а дальше используем переходы по суффиксным ссылкам. По доказанной [[#l5 | лемме]] переходов внутри фазы будет <tex>O(i)</tex> на текущей итерации. Следовательно, количество действий на одной итерации снижается с А так как фаза состоит из <tex>O(n^2)j</tex> до итераций, то амортизационно получаем, что на одной итерации будет <tex>O(n1)</tex>действий. Таким образом общая Следовательно, асимптотика алгоритма улучшилась до <tex>O(n^2)</tex>.