Чтобы построить дерево суффикса, в худшем случае, если все буквы строки различаются, сложность будет выглядеть как
n + (n-1) + (n-2) ... 1 = n*(n+1)/2
который является O (n ^ 2).
Однако, согласно http://en.wikipedia.org/wiki/Suffix_tree, построение дерева суффиксов занимает время O (n). Что мне здесь не хватает?
Ваша интуиция в том, почему алгоритм должен быть & Theta; (n 2), является хорошим, но большинство деревьев суффиксов разработаны таким образом, который устраняет необходимость этой сложности времени. Интуитивно вам показалось, что вам нужны и тета (n 2) разные узлы для хранения всех разных суффиксов, потому что вам понадобятся n + (n - 1) +... + 1 разные узлы. Однако деревья суффиксов обычно проектируются таким образом, чтобы в суффиксе не было ни одного символа node на символ. Вместо этого каждый край обычно помечен последовательностью символов, которые являются подстроками исходной строки. По-прежнему может показаться, что вам понадобится время & theta; (n 2), чтобы построить это дерево, потому что вам придется скопировать подстроки на эти ребра, но обычно этого избегают симпатичный трюк - поскольку все ребра обозначены строками, которые являются подстроками ввода, ребра вместо этого могут быть помечены стартовым и конечным положением, что означает, что символы edge spanning & Theta; (n) могут быть построены в O (1) раз и используя O (1) пространство.
Тем не менее, строить деревья суффиксов все равно очень сложно. Алгоритмы & Theta; (n), на которые ссылаются в Википедии, непросты. Одним из первых алгоритмов, найденных для работы в линейном времени, является Алгоритм Ukkonen, который обычно описывается в учебниках по строковым алгоритмам (например, Алгоритмы по строкам, деревьям и последовательностям). Оригинальная статья связана в Википедии.
Надеюсь, это поможет!