Самая длинная повторяющаяся подстрока с правильностью не менее k вхождений

Алгоритмы поиска самой длинной повторяющейся подстроки сформулированы следующим образом 1)build the suffix tree 2)find the deepest internal node with at least k leaf children Но я не могу понять, почему это работает, так что в основном, что делает этот алгоритм правильным? где n длина подстроки,это мне тоже непонятно!Давайте рассмотрим следующее дерево,здесь самая длинная повторяющаяся подстрока это "ru" и если применить поиск в глубину он найдёт её за 5 шаг а не за 2 Можете ли вы объясните мне этот материал? Спасибо

изображение


string algorithm longest-substring suffix-tree suffix-array
person ro.Loon    schedule 15.11.2016    source источник
comment
Он не может быть линейным по длине подстроки, поскольку построение суффиксного дерева линейно по длине самой строки.   -  person Rerito    schedule 21.11.2016

Ответы (2)


arrow_upward
0
arrow_downward

Я полагаю, вы прекрасно знаете, что O(n) (обозначение Big O) относится к порядок роста некоторой величины в зависимости от n, а не эквивалентность величины с n.
Пишу это, потому что читаю вопрос Я сомневался...
Я пишу это как ответ, а не как комментарий, так как это слишком длинно для комментария (я полагаю...)

person MarcoS    schedule 15.11.2016

arrow_upward
0
arrow_downward

Учитывая строку S из N символов, построение соответствующего дерева суффиксов занимает O(N) (с использованием такого алгоритма, как Укконена).

Теперь такое суффиксное дерево может иметь не более 2N - 1 узлов (включая корень и листья). ).

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

Какой-то псевдокод:

traverse(node, depth):
    nb_leaves <-- 0
    if empty(children(node)):
        nb_leaves <-- 1
    else:
        for child in children(node):
            nb_leaves <-- nb_leaves + traverse(child, depth+1)
    node.setdepth(depth)
    node.setoccurrences(nb_leaves)
    return nb_leaves

Начальный вызов traverse(root, 0). Поскольку структура представляет собой дерево, для каждого узла существует только один вызов traverse. Это означает, что максимальное количество вызовов traverse составляет 2N - 1, поэтому общий обход составляет всего O(N). Теперь вам просто нужно отслеживать узел с максимальной глубиной, который также проверяет: depth > 0 && nb_leaves >= k, добавляя соответствующий механизм учета. Это не мешает общей сложности.

В конце концов, сложность алгоритма поиска такой подстроки составляет O(N), где N — длина входной строки (а не длина совпадающей строки). подстрока!).

Примечание. Обход, описанный выше, в основном представляет собой DFS в дереве суффиксов.

person Rerito    schedule 15.11.2016