Самый низкий Внутренний Узел - Деревья Суффикса

Question

Поиск самого низкого внутреннего узла в случае деревьев суффиксов используется во многих приложениях.Например, самый низкий общий внутренний узел строк в обобщенном дереве суффиксов даст самую длинную общую подстроку.

Но я не мог придумать, как получить самый низкий внутренний узел в методе лучше, чем O (N * K) , где N = количество ключей и K = среднеедлина ключей .Есть ли более простой способ отслеживать этот узел?

Answer 1

http://en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_tree говорит, что O(N*K) действительно лучшее, что вы можете сделать с обычным деревом суффиксов.Однако он может быть предварительно обработан таким образом, чтобы облегчить ответ на вопрос.Это приводит к http://en.wikipedia.org/wiki/Lowest_common_ancestor, который имеет несколько ссылок на внешние алгоритмы.

Я бы предложил начать там.