string - 各スライディング ウィンドウ位置の辞書編集上の最初の固定サイズの部分文字列

Question

指定された文字列から、文字列内の同じサイズのすべての部分文字列の中で、辞書編集順序で最初に来る部分文字列 (いくつかの固定サイズ k) を見つけたいと思います。

非常に長い文字列 (サイズ m) のスライディング ウィンドウでこれを行い、文字列を移動するときにすべてのスライディング ウィンドウ (サイズ n > k) の位置に対してその部分文字列を見つけたいと考えています。

些細な解決策には m*O(n log(n)) 時間がかかるようです。

最初に通常の並べ替えを行い、最後のウィンドウ位置の先頭で始まる部分文字列を削除して、現在の末尾で終わる新しい部分文字列を挿入すると、 m*O(log(n)) に到達できると思いますウィンドウを移動するたびに、ウィンドウの位置を既にソートされた部分文字列のコレクションに追加します。（もちろん、部分文字列を別々に保存するのではなく、コレクション内の位置を維持するだけなので、必要なスペースは整数の nk だけになります）、

これにはより高速なアルゴリズムがありますか?

Answer 1

入力文字列のサイズを m、探している文字列の長さを n とします。接尾辞ツリーを使用すると、時間 O(m) でこれを解決できると思います。

まず、入力文字列のサフィックス ツリーを構築します。これには時間 O(m) がかかります。次に、各ステップで常に辞書順で最初の選択肢を選択して、ツリーで深さ優先検索を実行します。そうする過程で、見つけた長さ n の最初の文字列は、長さ n の辞書編集上の最初の部分文字列です。長さ m の文字列のサフィックス ツリーで DFS を実行すると O(m) の時間がかかるため、全体としては O(m) の時間がかかります。