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