3622
правки
Изменения
→Алгоритм за O(n3)
Алгоритм состоит из <tex>n</tex> итераций так как в исходном тексте <tex>O(n)</tex> суффиксов. На каждой фазе происходит продление всех суффиксов по порядку, что требует <tex>O(n^2)</tex> времени. Следовательно, общая асимптотика алгоритма <tex>O(n^3)</tex>.
'''Замечание:''' Казалось бына первый взгляд, что можно просто добавлять все суффиксы более логичным подходом кажется добавление всех суффиксов строки в дерево по очереди, и это уже было бы получив сразу алгоритм со временем работы <tex>O(n^2)</tex>. Но оптимизировать такой квадратичный алгоритм Однако улучшение данного алгоритма до линейного немного сложнеевремени работы будет намного сложней осуществить, хотя именно это в этом и делает заключается суть [[алгоритм Алгоритм МакКрейта | алгоритма МакКрейта]]. Оптимизируя описанный выше алгоритм, мы получим более простой алгоритм за <tex>O(n)</tex>.
== Продление суффиксов ==
