Изменения

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