275
правок
Изменения
→Псевдокод алгоритма за O(n3)
'''for''' i = 1 .. n
'''for''' j = 1 .. i
treeExtend(s[1j..ji]) <font color=green>// добавление текущего суффикса работает за линейное время</font>
</code>
'''Замечание:''' на первый взгляд, более логичным подходом кажется добавление всех суффиксов строки в дерево по очереди, получив сразу алгоритм со временем работы <tex>O(n^2)</tex>. Однако улучшение данного алгоритма до линейного времени работы будет намного сложней осуществить, хотя именно в этом и заключается суть [[Алгоритм МакКрейта | алгоритма МакКрейта]].
