Построение суффиксного дерева в иерархической памяти: различия между версиями

Пусть S[1, n] – строка, составленная из символов алфавита <math>\sigma \;</math>. Обозначим за <math>S_i \;</math> i-й суффикс строки S, за <math>lcp( \alpha, \beta) \;</math> – самый длинный общий префикс двух строк <math>\alpha \;</math> и <math>\beta \;</math>, а за lca(u, v) – наименьшего общего предка двух вершин u и v в дереве.

Суффиксное дерево S[1, n], которое далее будет обозначаться <math>\mathcal{T}_S \;</math>, представляет собой дерево, хранящее все суффиксы S# в компактной форме, где # <math>\notin \Sigma \;</math> – специальный символ (см. рис. 1). <math>\mathcal{T}_S \;</math> содержит n листьев с номерами от 1 до n, и любой путь из корня до листа читается как суффикс S#. Маркер конца # гарантирует, что ни один суффикс не является префиксом другого суффикса в S#. Каждая внутренняя вершина имеет по меньшей мере двух потомков; каждое ребро помечено непустой подстрокой из S. Никакие два ребра, выходящие из одной вершины, не могут начинаться с одной и той же буквы; вершины-братья лексикографически упорядочены в соответствии с этими буквами. Метки ребер закодированы парами целых чисел; например, S[x, y] представлено парой hx;yi. В результате все <math>\Theta(n^2) \;</math> подстрок S можно представить в O(n)-оптимальном пространстве при помощи структуры <math>\mathcal{T}_S \;</math> и кодирования ребер. Кроме того, обход листьев суффиксного дерева справа налево дает упорядоченное множество суффиксов S, также известное как суффиксный массив [12]. Заметим, что случай большого набора строк Л = fS1 ; S2..: ; Skg сводится к случаю одной длинной строки S = S1#1S2#2 • • • Sk#k, где #i6 2 £ – специальные символы.