c# - 接尾辞ツリーを使用した一意の部分文字列

Question

S指定された長さの文字列の場合n-

• のすべての一意の部分文字列を見つけるための最適なアルゴリズムは、S未満にすることはできませんO(n^2)。したがって、最適なアルゴリズムは の複雑さを提供しO(n^2)ます。私が読んだことによると、これは のサフィックスツリーを作成することで実装できますS。

S のサフィックス ツリーは、時間内に作成できますO(n)。さて、私の質問は-

SS の接尾辞ツリーを使用して、 inの一意の部分文字列をすべて取得するにはどうすればよいO(n^2)でしょうか?

Answer 1

接尾辞配列について読んでみてください：http：//en.wikipedia.org/wiki/Suffix_array このメソッドは、文字列内の部分文字列を取得するための接尾辞ツリーよりも高速です。

Answer 2

トライすることで最適に行うことができます。試行する文字列を追加し、ルートからノードまでトラバースします。各ルートからノードへのパスは、文字列のサフィックスを示します。これらのサフィックスのすべてのプレフィックスを取ります。これらは一意の部分文字列です。