シフト文字列のデータ構造

Question

バイナリ文字列のデータ構造に興味があります。 S = s s .... s _mは、サイズmのバイナリ文字列であるとします。 Shift(S,i)は、文字列の循環シフトで、左にスペースがあります。Siすなわち、シフト（S、i）はsの _I S _{I + 1} S _{I + 2} ... S _メートル S ... _I-1 S =、です。サポートし、効率的なデータ構造を示唆している：（1）

Insert(s)がOでDSのバイナリ文字列を挿入Oでempy DSの

1. Init()を
2. Search_cyclic(s)か否かを調べる（|^2 | S） O（| s |）にANY iのShift(S,i)があります。

スペース複雑さ：O（| S | + | S | + ..... + | S _メートル |）S _私は1メートルの文字列を、私たちの場合でありますこれまでこれを挿入した。

いくつかのiについてSearch_cyclic（s、i）を見つけなければならない場合、これはサフィックスツリーを使用してO（| s |）内を単にトラバースするだけで非常に簡単です。しかし、ここではSearch_cyclic（s）には与えられたiがないので、与えられた複雑さで何をすべきかわかりません。 OTOH、Insert（s）は一般にO（| s |）をサフィックスツリーに挿入するために必要であり、ここではO（| s |^2）が与えられます。

Answer 1

ここに私があなたに提案できる解決策があります。複雑さは、あなたが求めたものよりも低くなりますが、少し複雑に思えるかもしれません。

すべての文字列を保持するデータ構造はTrie、さらにはPatricia treeになります。各文字列のこのツリーでは、考えられるすべてのシフトのうち最小のサイクリックシフト（つまり、辞書編集的に最小のものすべての循環シフト）を挿入します。線形時間の文字列の最小巡回シフトを計算することができます。後でもう一度考えてみましょう。あなたがそれをやることができると仮定してください。ここで必要な操作を実装する方法はありません：

1. のInit（） - トライとパトリシア両方のツリーの初期化に一定している - 何の問題ここ
2. 挿入（S） - あなたは最小限の巡回シフトs'を計算しますO（| s |）のデータ構造体のいずれかに挿入します（O（| s |）= O（| s |））。これは必要な複雑さよりも優れています
3. Search_cyclic - 再びO（| s |）のsの最小循環シフトを計算し、文字列が存在すればPatriciaまたはTrieをチェックインします。

また、パトリシアを構築する場合、メモリの複雑さは必要に応じて低くなります。

残っているのは、最小サイクリックシフトを見つける方法を説明することだけです。接尾辞の木について言及して以来、私はあなたがそれを構築する方法を知っていることを願ってlinear time。つまり、あなたの文字列sを自分自身に追加します（つまり、それを二重にして）、二重の文字列のサフィックスツリーを作成します。これは| s |についてはまだ線形です。だから問題はない。その後、このツリーで長さnの接尾辞の最小値を見つけるだけです。これは難しいことではありません。ルートから始め、最小の文字列が書かれている現在のノードから常にリンクをたどって、長さを長くしてから| s |を累積します。文字列が2倍になるため、少なくとも| s |の長さが累積されるまで、最小限の文字列リンクに従うことができます。

この回答が役立ちます。