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

Question

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

образ

Answer 1

Для строки 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 в дереве суффиксов.

Answer 2

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