最低內部節點 - 後綴樹

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有多個鏈接到外部算法。

我會建議從那裏開始。