最長繰り返し部分文字列を見つけるためのアルゴリズムは、次のように書かれています 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個のオカレンスを持つ最長繰り返し部分文字列
0
A
答えて
0
私はあなたが完全にO(n)(ランダウの記号を)知っていると仮定はn個の機能、およびないようにと量の等価性をいくつかの量の成長の順序を指し、 n。
私は(私は...と仮定)はコメントを少し長すぎるので、私はaswerではなく、コメントとしてこれを書いている
...これは私が疑問にあった質問を読んbecase書く
0
文字列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です。
関連する問題
- 1. 最小値と最大値を持つk個の部分の分割
- 2. 文字列の最長部分文字列を持つ行を選択
- 3. 最大最大繰返し部分文字列
- 4. 繰り返し文字列を持つ文字列python
- 5. 最も長い繰り返し文字列を検索しますか?
- 6. 最も長い繰り返し文字の位置を見つける
- 7. 文字列内の最も長い繰り返し1の長さを見つける
- 8. 文字列から繰り返し部分文字列を削除します。
- 9. 繰り返し文字列部分の間の値
- 10. 文字列から繰り返し部分文字列を取得する
- 11. パスワードの正規表現(少なくとも2桁と特殊文字1個、最小長8)
- 12. 最も長い共通部分文字列問題
- 13. アルファベット順に最長の部分文字列を見つける
- 14. 3つの文字列の中で最も長い共通部分シーケンス
- 15. 文字列またはテーブルcoulmnで未知の繰り返し部分文字列を見つける方法
- 16. 文字列中で最も長い連続した部分文字列を見つける方法は?
- 17. 文字列内の文字繰り返しの長さと位置の決定
- 18. 最初の非繰り返し文字列を返します
- 19. LeetCode Problem3:最長サブストリング文字の繰り返し
- 20. で文字列の繰り返し文字を見つける
- 21. 正規表現の文字列繰り返しの長さ
- 22. 接尾辞ツリー(バイナリ文字列):最も長い部分文字列を見つけよう
- 23. 再帰とDPを使用する最も長い共通部分文字列
- 24. どのように文字列の最初のオカレンスを繰り返してPythonを削除するには?
- 25. 文字列内に繰り返し文字を見つける
- 26. 繰り返しタグへの部分文字列オフセットを操作する方法
- 27. Perlは最も効果的な方法で繰り返しパターンに文字列を分割しますか?
- 28. 正規表現内の繰り返し部分文字列のマッチング
- 29. 文字列から固定長の部分文字列を返す方法は?
- 30. 範囲からの部分文字列のうちの少なくとも1つを含む文字列を見つける
サフィックスツリー構造は文字列自体の長さが線形であるため、部分文字列の長さは線形にできません – Rerito