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