最長の繰り返し部分文字列を見つけるためのアルゴリズムは次のように定式化されます
1)build the suffix tree
2)find the deepest internal node with at least k leaf children
しかし、なぜこれが機能するのか理解できません。基本的に、このアルゴリズムが正しいのはなぜですか?また、このアルゴリズムを見つけたソースは、O(n) で繰り返される部分文字列を見つけるここで、n は部分文字列の長さです。これも私には明確ではありません!次のツリーを考えてみましょう。ここで、最も長く繰り返される部分文字列は「ru」であり、DFS を適用すると、5 ステップで検出されますが、2 では検出されません。あなたは私にこのことを説明しますか？ありがとう
2 に答える
0
O(n) (Big O 表記法) は、 nとの量の等価性ではなく、nの関数としての量の成長の順序を指すことを完全に知っていると思います。
私が疑問に思っていた質問を読んだので、
これを書きます...コメントには少し長すぎるので、これをコメントではなく回答として書いています（私は推測します...）
于 2016-11-15T15:29:41.170 に答える