497
правок
Изменения
→Шаг 2: построение чётного дерева
[[Файл:Tree101232even-pre.png|300px|Раскрываем все пары в суффиксы]]
'''Рис. 2 дерево с раскрытыми парами в суффиксы'''
Корректируются все развилки дерева (так как они могут совпадать в первых символах):
[[Файл:Tree101232even.png|300px|Корректируются все развилки дерева (так как они могут совпадать в первых символах)]]
'''Рис. 3 все развилки скорректированы'''
Итак, если <tex>T(n)</tex> {{---}} это время, которое потребуется нашему алгоритму, чтобы построить суффиксное дерево для строки <tex>S</tex>, то <tex>T_{even}</tex> может быть построено за время <tex>T(n/2) + O(n)</tex>
