Нахождение самого длинного двойного суффикса за линейное время

Question

Учитывая строку sнайди самый длинный двойной суффикс во временной сложности O(|s|),

Пример: для строки bananaLDS это na, За abaabaa его baa,

Очевидно, я думал об использовании дерева суффиксов, но мне трудно найти в нем двойной суффикс.

Answer 1

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

Но так как вы упомянули деревья суффиксов, давайте рассмотрим решение, основанное на деревьях суффиксов! Я предполагаю, что вы используете маркер конца, чтобы отметить конец строки (строк), которые вы вставляете в дерево. Чтобы проиллюстрировать это, вот представление дерева суффиксов, созданного для вашего abaabaa пример:

$ - ##
b a a - $ - ## // Longest double suffix: P is the first dash, N the second
        b a a $ - ## // N' is the dash
a - $ - ##
    a - $ - ##
        b a a $ - ##
    b a a - $ - ##
            b a a $ - ##

Когда N является узлом в дереве суффиксов, мы будем обозначать |N| длина подстроки, представленная N.

Как вы можете охарактеризовать "двойной суффикс" в дереве суффиксов? Ну, это конечный узел N с родительским узлом, который обладает определенным свойством: пусть P будет родительским узлом с двойным суффиксом, тогда:

• P имеет переход к суффиксному узлу N, который содержит только маркер конца ($ выше) строки.
• Пусть суффикс будет подстрокой, представленной узлом P с добавленным маркером конца (baa$ в твоем примере). Если мы спустимся по дереву от P, используя суффикс, мы окажемся в другом узле суффикса N' (ходить по дереву на самом деле не нужно)
• Подстрока, представленная узлом P, представляет собой двойной суффикс (baa в нашем случае).
• У нас есть равенства | N'| = 2.|P| + 1 и |N| = | P | + 1

Учитывая это, вам нужно только перебрать узлы суффикса и проверить это условие. Вы можете быть жадным, если перебираете суффиксы в порядке убывания длины: первое совпадение обязательно является самым длинным двойным суффиксом.

Обратите внимание, что мы можем остановить наш поиск после проверки суффикса длины |S|/2 и перебирать только суффиксы нечетной длины (не забывайте, что мы добавляем маркер конца в строку)

Анализ сложности

Построение дерева суффиксов O(|S|),
Пусть N' будет суффиксным узлом и N быть узлом суффикса для суффикса длины (| N'| -1) / 2 + 1. Предполагая правильное построение дерева:

• Суффиксы могут храниться в массиве / векторе в возрастающем порядке, потому что создание дерева добавляет их в порядке возрастания длины (по крайней мере, с помощью алгоритма Укконена).
• Таким образом, доступ к суффиксу длины k O(1)
• Доступ к подстроке, представленной узлом дерева, O(1), в частности, это относится к P родительскому узлу N и N'
• Выяснить, содержит ли переход от P к N только маркер конца ($) является O(1)
• Проверка, если | N'| = 2.|P| +1 действительно O(1)

Поскольку мы перебираем суффикс в порядке убывания длины, мы обязательно сосредоточимся на N' суффиксы (удвоенный суффикс, т.е. baabaa$ в вашем примере), поэтому нам просто нужно:

• Получить N суффиксный узел такой, что |N'| = 2.|N| - 1: O(1)
• Получить P родительский узел суффикса N: O(1)
• Убедитесь, что переход от P к N содержит только маркер конца $: O(1)

Доказательство: (Мы игнорируем маркер конца в следующем доказательстве)

Три вышеприведенных шага, если они приводят к истинной оценке, доказывают существование суффикса длины 2.|P| которая начинается с подстроки, представленной буквой P, которая также является суффиксом. Поскольку эта подстрока является суффиксом, суффикс длины 2.|P| обязательно заканчивается этим и поэтому состоит из двух вхождений этой подстроки QED.

Так как мы сделаем этот шаг самое большее (|S|/2 + 1)/2 суффиксы, поэтому шаг идентификации O(|S|) в худшем случае.

Таким образом, общая сложность O(|S|),

Answer 2

Переверните строку и создайте разреженный массив P[i][j], где i из 0 в log(n), j из 0 в n-1, n длина строки P[i][j] относится к рангу суффикса, начиная с позиции j и длина 2^i, Так что если P[i][j]=P[i][k], первый 2^i символы суффиксов в индексах j а также k равны.

Теперь ваша проблема сводится к поиску самого длинного общего префикса для 0(начало обратной строки) и другой суффикс в индексе iтакой, что LCP >= i, Где LCP можно вычислить, просто используя P массив в log(n) время, сравнивая первый 2^x символы этих двух суффиксов и постепенно сокращаются x,

Общая сложность n*log(n)*log(n), Вот рабочий исходный код C++: https://ideone.com/aJCAYG