Могут ли суффиксные деревья использоваться для поиска всех общих подстрок?

Я пытаюсь использовать деревья суффиксов для сравнения последовательностей строк. Я нашел реализации / теорию для самой длинной общей проблемы подстроки, используя деревья суффиксов. Однако, то, что я ищу, является обсуждением связанной проблемы - "все общие подстроки". В частности, у меня есть проблема, в которой мне нужно сначала найти самую длинную общую подстроку, затем найти следующую самую длинную общую подстроку, которая не включает в себя уже найденные индексы lcs, и так далее до минимальной длины. Решается ли эта проблема путем построения Обобщенного дерева суффиксов (GST) только один раз для двух последовательностей. Я знаю, что это можно решить путем многократного построения GST после каждой итерации поиска и удаления LCS. Но мне интересно, если я упускаю изящный трюк, где в GST построен только один раз.

Да, деревья суффиксов могут использоваться для поиска всех общих подстрок. Я бы сказал, что вместо этого следует использовать массив суффиксов, но если у вас уже есть дерево суффиксов, построение массива суффиксов из дерева суффиксов требует DFS линейного времени. Таким образом, остальная часть моего ответа будет предполагать, что мы работаем с массивом суффиксов.

Дан текстовый , массив суффиксов для S - это массив целых чисел в диапазоне от 0 до n, определяющий лексикографический порядок суффиксов n + 1 строки S $$S = s_1 , ..., s_n$$S$$0$$n$$n+1$$S$

Мы хотим связать массив суффиксов с , самыми длинными общими префиксами. Мы можем построить массив L C P s за линейное время, как упомянуто в статье Kasai et al . Суффиксные массивы и их массивы lcp выстраиваются вместе таким образом, что при заданном индексе в массив lcp говорят, что l c p [ k ], где k - номер индекса, тогда s a [ k ] будет началом одного экземпляра общего подстрока и s a [ k - 1 $LCPs$$LCPs$$lcp[k]$$k$$sa[k]$$sa[k-1]$будет начальным индексом второго экземпляра. Длина, конечно, является значением в массиве lcp.

У меня есть идея, которая может сработать. Начну с обобщенным деревом суффиксов для последовательностей и T . Каждый внутренний узел с суффиксами S и T в своем поддереве соответствует некоторой общей подстроке последовательностей. Будем называть такие узлы нетривиальными. Общая подстрока максимальна, если соответствующий узел не имеет нетривиальных дочерних элементов. Если узел v нетривиален, мы сохраняем наибольшую глубину строки нетривиального узла в его поддереве как l c s ( v ) . Если r - корень, то l c s ( r $S$$T$$S$$T$$v$$lcs(v)$$r$$lcs(r)$длина самой длинной общей подстроки и T .$S$$T$

Обновление дерева после удаления подстроки из одной из последовательностей не должно быть слишком сложным. Сначала мы удаляем листья, соответствующие удаленным суффиксам, обновляя их предков, когда это необходимо. Затем мы начинаем обрабатывать суффиксы, предшествующие удаленной подстроке. Пусть будет наименьшим нетривиальным предком текущего листа. Если длина суффикса равна k (мы k шагов от удаления) и k < l c s ( v ) , мы должны переместить суффикс в его правильное положение в дереве, обновляя предков при необходимости. Если k ≥ l c s ( v $v$$k$$k$$k < lcs(v)$$k \ge lcs(v)$Мы закончили, так как нас не интересуют поддеревья с тривиальными корнями.

Общий алгоритм многократно находит самую длинную общую подстроку и T и удаляет одно из его вхождений из обеих последовательностей, если длина LCS достаточно велика.$S$$T$

Есть некоторые технические детали, но общая идея должна работать.

Начните с каскадным текстом S $ T , где $ не происходит нигде в * или Т . Построить суффиксное дерево / массив из этого текста. Теперь легко обойти эту суффиксную структуру данных, чтобы собрать все правильные максимальные повторы. Исследуя левый контекст, отфильтруйте не левые максимальные повторы. Эта фильтрация влево может быть реализована с использованием таблицы Burrows-Wheeler, как в Abouelhoda и др., Хотя я не считаю, что это необходимо. Повторяется только в S или только в Tследует также устранить на этом этапе. Повторения, которые не были устранены, затем помещаются в очередь с приоритетом, приоритет определяется длиной. После прохождения, поскольку записанные повторы удаляются из приоритета, может быть выполнена окончательная фильтрация (для удержания подстроки). Однако, учитывая использование максимальных фраз, я подозреваю, что очень мало этой фильтрации будет необходимо.

Этот алгоритм - мое собственное изобретение. Я бы не назвал это очень умным, но это должно сработать.

$S$$s$$T$$t$$s$$t$$S$$T$