Изменения

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