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

Пусть S[1, n] – строка, составленная из символов алфавита S. Обозначим за Si i-й суффикс строки S, за lcp(a, j$) – самый длинный общий префикс двух строк a и jS, а за lca(u, v) – наименьшего общего предка двух вершин u и v в дереве.

Суффиксное дерево S[1, n], которое далее будет обозначаться TS, представляет собой дерево, хранящее все суффиксы S# в компактной форме, где # $ £ – специальный символ (см. рис. 1). TS содержит n листьев с номерами от 1 до n, и любой путь из корня до листа читается как суффикс S#. Маркер конца # гарантирует, что ни один суффикс не является префиксом другого суффикса в S#. Каждая внутренняя вершина имеет по меньшей мере двух потомков; каждое ребро помечено непустой подстрокой из S. Никакие два ребра, выходящие из одной вершины, не могут начинаться с одной и той же буквы; вершины-братья лексикографически упорядочены в соответствии с этими буквами. Метки ребер закодированы парами целых чисел; например, S[x, y] представлено парой hx;yi. В результате все &(n2) подстрок S можно представить в O(n)-оптимальном пространстве при помощи структуры TS и кодирования ребер. Кроме того, обход листьев суффиксного дерева справа налево дает упорядоченное множество суффиксов S, также известное как суффиксный массив [12]. Заметим, что случай большого набора строк Л = fS1 ; S2..: ; Skg сводится к случаю одной длинной строки S = S1#1S2#2 • • • Sk#k, где #i6 2 £ – специальные символы.