Ваша интуиция, объясняющая, почему алгоритм должен быть & Theta; (n 2 ), хороша, но большинство деревьев суффиксов спроектированы таким образом, что устраняет необходимость в этой временной сложности. Интуитивно кажется, что вам нужны & Theta; (n 2 ) разные узлы для хранения всех разных суффиксов, потому что вам нужно n + (n - 1) + ... + 1 разных узлов , Однако суффиксные деревья обычно разрабатываются так, чтобы в суффиксе не было ни одного узла на символ. Вместо этого каждое ребро обычно помечается последовательностью символов, которые являются подстроками исходной строки. Может показаться, что вам понадобится время для создания этого дерева, потому что вам нужно скопировать подстроки к этим краям, но обычно этого избегает симпатичный трюк - поскольку все ребра помечены строками, которые являются подстроками ввода, вместо этого ребра могут быть помечены начальной и конечной позицией, что означает, что символы, охватывающие ребра & Theta; (n), могут быть созданы за время O (1) с использованием O (1) пробел.
Тем не менее, построить суффиксные деревья все еще очень сложно. Алгоритмы & Theta; (n), на которые есть ссылки в Википедии, не легки. Один из первых алгоритмов, работающих на линейном времени, - Алгоритм Укконена , который обычно описывается в учебниках по строковым алгоритмам (например, Алгоритмы на строках, деревьях и последовательности ) . Оригинал статьи связан в Википедии. Более современные подходы работают, сначала создавая массив суффиксов и используя его для построения дерева суффиксов.
Надеюсь, это поможет!