Найдите самую длинную подстроку в двух словах с деревом суффиксов

#string #algorithm #data-structures #tree #suffix-tree

Вопрос:

Мне нужно решить проблему — найти самую длинную подстроку в двух словах с деревом суффиксов. Я построил суффикс для первого и второго слова, но как я могу найти самую длинную подстроку в двух словах? Не могли бы вы предложить возможный алгоритм решения этой проблемы?

Ответ №1:

Хитрость в том, чтобы использовать одно дерево суффиксов для обоих слов:

Сначала используйте какой-нибудь нестроковый символ, например $ или # или что-то еще (не должно быть частью какой-либо строки), чтобы соединить строки
т. е. строки abra и abracadabra присоединяются к abra$abracadabra#
Затем постройте из этого дерево суффиксов.
Теперь от листьев, заканчивающихся на $ «поднимитесь», и отметьте узлы как часть word1
Сделайте то же самое для листьев , заканчивающихся на # , пометив их как часть слова2
Теперь мы можем выполнить простой DFS обход от корня, так как самая длинная подстрока будет некоторым путем от корня (только проверка узлов, которые являются частью обоих слов).

Сложность — O(a b) (построение дерева суффиксов (если построить быстрым способом) O(a b) (dfs) = O(a b)

1. Обобщенное дерево суффиксов-это правильный путь, но DFS и пропуска путей с помощью sentinel недостаточно. Вы определенно не хотите искать дальше$, так как это не будет общей строкой, но есть и другие строки, которые также не являются общими. Если строка представляет собой$bbbb, то самая длинная строка без $ — это bbbb, которая встречается только один раз. Вам нужны только внутренние узлы. Но там самый длинный — bbb. Вам нужны внутренние узлы с листьями из обеих строк. Сначала DFS определит, у каких узлов есть дочерние элементы в обеих строках, а затем DFS определит повторы, и все равно в O(a b)