最長繰り返し部分文字列を見つけるためのアルゴリズムは、次のように書かれています 1)build the suffix tree 2)find the deepest internal node with at least k leaf children しかし、なぜこのアルゴリズムが正しいのか理解できません。アルゴリズムでは、O（n）に繰り返し部分文字列があると言いますが、nは部分文字列の長さですが、これも私には分かりません！次のツリーを考えてみましょう。ここでは最長繰り返し部分文字列は "ru" DFSでは5ステップでは見つかるが2では見つからない このことを私に説明できますか？ おかげ少なくともk個のオカレンスを持つ最長繰り返し部分文字列
私はあなたが完全にO(n)（ランダウの記号を）知っていると仮定はn個の機能、およびないようにと量の等価性をいくつかの量の成長の順序を指し、 n。
私は（私は...と仮定）はコメントを少し長すぎるので、私はaswerではなく、コメントとしてこれを書いている
...これは私が疑問にあった質問を読んbecase書く
文字列SがN文字の場合、対応する接尾辞ツリーの作成は、Ukkonen'sなどのアルゴリズムを使用して、O（N）です。
このような接尾辞ツリーは、at most 2N - 1 nodes（ルートと葉を含む）を持つことができます。
ツリーをたどって、特定のノードから到達可能なリーフの数とその深さを計算すると、望ましい結果が得られます。これを行うには、ルートから始めて、それぞれの子を探索します。
いくつかの擬似コード：
traverse(node, depth):
nb_leaves <-- 0
if empty(children(node)):
nb_leaves <-- 1
else:
for child in children(node):
nb_leaves <-- nb_leaves + traverse(child, depth+1)
node.setdepth(depth)
node.setoccurrences(nb_leaves)
return nb_leaves
最初の呼び出しはtraverse(root, 0)です。構造体はツリーなので、ノードごとにtraverseを1回呼び出すだけです。これは、traverseへの最大呼び出し回数が2N - 1であることを意味します。したがって、全体のトラバーサルはO（N）です。今度は、最大深度を持つノードを追跡するだけでよい：depth > 0 && nb_leaves >= k関連する簿記メカニズムを追加することによって、確認する。これは、全体の複雑さを妨げるものではありません。最後に
、そのようなサブストリングを検索するためのアルゴリズムの複雑さは、O（N）Nは、入力された文字列の長さである（としないサブストリングマッチングの長さ！）。
注：上記トラバーサルは、基本的に接尾辞ツリー上のDFSです。
サフィックスツリー構造は文字列自体の長さが線形であるため、部分文字列の長さは線形にできません – Rerito