Можно сказать, что предыдущая часть. Даже если вы считаете, что знакомы с суффиксным деревом, рекомендую просмотреть код внизу.

Всем привет! Наконец, я до него добрался :)

В данной статье я хотел бы избежать длинных и сложных теоретических выкладок, которые долго отпугивали меня от данного алгоритма. Так что сразу к делу. Доказательств приводить не буду, а больше внимания уделю особенностям реализации. Доказательства поищите где-нибудь на stackoverflow (лично я черпал знания об алгоритме именно оттуда) или на wiki-конспектах ИТМО или в книге Гасфилда или в конспекте Юрия Лифшица... Или ещё где-нибудь, где таким любят заниматься.

Суффиксным деревом будем называть суффиксный бор, сжатый таким образом, что вершина присутствует в дереве в том и только том случае, если в суффиксном боре у неё было больше одного сына или если она отвечает одному из суффиксов строки.

Теперь о самом алгоритме. На каждой итерации он поддерживает так называемое неявное суффиксное дерево. В нём критерием существования вершины является только то, что у неё больше одного ребёнка, то есть "терминальные" вершины могут быть опущены. Обычно рёбра при построении суфф дерева хранят в виде пары [L_i, R_i]. Лично мне не очень удобно работать с ними в таком виде, поэтому предлагаю вместо этого в каждой вершине дерева хранить такие данные о ребре, которое ведёт в неё — fpos_i — первая позиция вхождения ребра в строку и len_i — соответсвенно, длина ребра. При этом длину рёбер, ведущих в листья будем по-умолчанию считать равной inf. Таким образом мы можем быть уверены, что в любой момент времени рёбра в листья идут до самого конца строки. Корнем дерева будет вершина под номером 0.

На каждом шаге алгоритма будем хранить самый длинный неуникальный суффикс строки. Для этого будем хранить пару чисел (node, pos) — вершину в суфф дереве, которая ему соответствует и число символов, которое необходимо пройти от неё вниз для получения этого суффикса. Изначально считаем node = pos = 0. При дописывании нового символа мы увеличим pos на 1 и добавим все уникальные суффиксы строки, которые возникли после добавления нового символа.

Также нам понадобится понятие суффиксной ссылки. Она определена для внутренних вершин дерева. Переход по суффиксной ссылке будет вести в вершину, соответствующую той же строке, но без первого символа. Для корня суффиксная ссылка не определена.

Добавление будет состоять из следующих этапов:

1. Если pos = 0, то все суффиксы обработаны. Завершаемся. Иначе найдём вершину, после которой находится новый суффикс. То есть, пока pos больше длины ребра, исходящего из данной вершины, будем идти по ребру и вычитать его длину из pos.
2. Пытаемся добавить очередной суффикс. Здесь нас ожидает три варианта.
   1. Если у нас нет исходящего ребра по интересующему нас символу, то мы просто создаём новую вершину и подвешиваем её к текущей.
   2. Если ребро есть и суффикс, который мы хотим добавить целиком лежит на нём, завершаем свою работу — этот и дальнейшие суффиксы не являются уникальными.
   3. Если ребро есть и суффикс не лежит на нём целиком, это значит, что нам нужно создать новую вершину посередине этого ребра, к которой подвесить старую вершину с конца ребра и новую вершину, соответствующую суффиксу. Стоит заметить, что ребро к новому листу в данный момент будет иметь длину, равную единице.
3. Если мы не завершили работу на прошлом шаге, переходим к следующему суффиксу. Если мы находимся в корне, то мы уменьшаем pos на единицу, иначе же мы просто переходим по суффиксной ссылке node = link(node). После этого мы переходим к пункту 1.

Отдельно о пересчёте суффиксной ссылки. На i-ом этапе мы будем устанавливать суффиксную ссылку для внутренней вершины, созданной i - 1-ом. Если мы создаём новую внутреннюю вершину, то суффиксная ссылка будет вести в неё. В двух остальных случаях суффиксная ссылка ведёт в node (Мне лень расписывать поистине чудесное доказательство, поэтому оно оставляется любопытному читателю в качестве домашнего упражнения).

На этом описание алгоритма заканчивается и мы переходим к его реализации.

Код: #sT8Vd1

Я постарался сделать код настолько простым и понятным, насколько это вообще возможно :) Не знаю, насколько у меня получилось, надеюсь на ваши отзывы и вопросы.