Suffix Tree (Binary String): найти самую длинную подстроку

Question

В поисках эффективного алгоритма для поиска самой длинной подстроки в строке, которая также имеет свою дополнительную строку (поразрядно).

То, что я имею в виду, говоря побитовую строку:

100011
011100

Answer 1

Вот простой алгоритм O (n), который основан на построении суффиксного дерева.

Загрузка исходной строки s и строки дополнения s 'в одно и то же дерево суффиксов (O (n) time). Затем постобработайте это дерево, установив для каждого узла x два флага f (x) и f '(x), которые истинны именно тогда, когда f (x) (соответственно f' (x)) содержит суффикс s (соответственно s'). Теперь просто обойдите дерево, ища самый глубокий узел, для которого установлены оба флага, и вы нашли самую длинную строку в s, дополнение которой также встречается в s. Постобработка также стоит только O (n) времени, поэтому общее время выполнения O (n).

Answer 2

Следующий алгоритм - наихудший случай O(n * n), а средний случай - просто суперлинейный. Это наихудший случай, когда много длинных общих подстрок.

Рассмотрим набор подстрок, которые можно сформировать, начиная с произвольной точки в вашей строке. Создайте три из тех подстрок, которые заканчиваются указателем на местоположение в исходной строке, если есть только одно возможное совпадение. Вы должны поработать над этим триом для каждой из n подстрок, но вам нужно выполнить только самую длинную общую подстроку, которая есть в этой строке среди других.

Как только вы построите эту структуру данных, выполните рекурсивный обход дерева, ища пару подстроки с ее дополнением. Структура дерева должна сделать это соединение очень эффективным, так как вам нужно только соединить противоположные подстроки, а не подстроки со всеми другими местами в строке, которые могут быть.

Если некоторые символы встречаются часто, а их дополнения необычны, вы можете улучшить производительность, лениво создавая дерево.