私は、バイナリ文字列をデータ構造体（insert関数）に格納する最も効率的な方法を探しています。文字列を取得するときに、指定された文字列の循環文字列が私の構造体にあるかどうかをチェックします。サイクリック文字列を検索
入力文字列をTrieに格納することを考えましたが、文字列の循環文字列がTrieに挿入されたかどうかを判断しようとすると、| s |可能なすべての循環文字列をTrieで検索します。
場所の複雑さはTrieのようになりますが、それを効率的に行う方法はありますか？
注：私は、たとえば1011のすべての巡回の文字列であることを私は意味の文字列の巡回文字列を言うときは：0111, 1110, 1101, 1011
次に基づいて巡回文字列のcanonicalizing機能を思い付くことができます：
これは辞書順最小値に等価クラスのすべて（1011、1101、1110、0111）を正規化します：0111
0101010101このアルゴがうまく実行しないであろうために厄介な例ですが、あなたのビットがおおまかにランダムに分布しているなら、実際には長い文字列でうまくいくはずです。
標準形式に基づいてハッシュを作成したり、空の文字列と0から始まる文字列のみを含むトライを使用して、単一のトライを実行すると質問に答えることができます。
EDIT：
私は長さの文字列を持っている場合、| S |それは、辞書編集上の価値が最小限であることを見つけるのに多くの時間がかかる可能性があります。
だからこそ、私は010101....が悪い結果を出していると言いました。文字列の長さがnで、長さが1の文字列の長さがrであるとします。ビットがランダムに分布している場合、最長ランの長さは"Distribution of longest run"によるO（log n）です。
最長の実行時間はO（n）です。バッファコピーの代わりにオフセットを使用してシフトを実装することができます。これはO（1）でなければなりません。ランの数は最悪の場合O（n/m）です。
そして、ステップ3を実行する時間が
これは、O（n2）の最悪の場合があるが、O（n + log2n）≒O（n）の平均の場合をもたらす。
私は理解しません。 1100010が格納され、1001が検索されると仮定します。あなたのアルゴリズムはどのように進んでいますか？部分文字列1100を見つけることはできますか？ –
いいえ、サイクリック文字列の部分文字列は解決しませんが、部分文字列についてはOP内に何も表示されません。 –
ええと、私の解釈は「私の構造の中にいくつかの周期的なものがあるかどうかを調べる」という点が異なります。おそらく、user550413が明らかにするでしょう。 –
あなたはn個の文字列s1..snを持ち、tの循環置換が任意のs1..snの部分文字列かどうかを知りたい文字列tを与えられます。また、ストリングをできるだけ効率的に保管したいとします。私はあなたの質問を正しく理解しましたか？
これは解ですが、実行時間が長い場合：与えられた入力tに対して、s1..snのすべてのsをt '= concat（t、t）、check t' t 'とsmの最長部分列が少なくとも| t | | si | = k、| t | = lそれはO（n.k.l）時間で実行されます。また、s1..snを任意のデータ構造に格納することができます。それは十分ですか、それともあなたですか？
これが2文字以上のアルファベットの場合、文字値の順序にかかわらず同じ結果を生成するハッシュ関数を作成すると、ほとんどの不一致を素早く排除できます。 –
@ C.Evenhuis：いいえ、バイナリ文字列のみで作業しています。 – user550413
すべての挿入を先に行いますか？または、挿入と参照を混在させますか？ – templatetypedef