サフィックスツリーによってO（n）時間に宿題を解決するアルゴリズムを実装する方法は？

Question

私はバイオインフォマティクスに質問があります。サフィックスツリー構造で解決できます。

文字列S = S [1 ... n]と番号kが与えられた場合、S内で発生するSの最小の部分文字列が存在する場合、それを正確にk回探したいと考えます。 O（n）時間にこの問題を解決するには？

Answer 1

文字列O（N）の接尾辞ツリーを構築します。

すべてのノードについて、その下のリーフ数をO（N）とカウントします。

count == kのノードを検索します。ルートからそのノードまでのパスは、正確にk回繰り返すサブストリングです。