サフィックスツリーから元の文字列を効率的に取り出す方法は？

Question

文字列の接尾辞ツリーがあり、接尾辞ツリーがukkonenの接尾辞ツリーでない場合、つまり、エッジラベルが文字列である通常の接尾辞ツリーが与えられます。どのように効率的にそのサフィックスツリーから元の文字列を取得するには？

Answer 1

元の文字列は最長の接尾辞です。したがって、深さ優先の検索を行うだけでツリー内の最も長い文字列のノードを見つけることができます。