最下位内部ノード - 接尾辞ツリー

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につながります。

私はそこから始めることを提案します。