7

バイナリ文字列をデータ構造に格納する最も効率的な方法（関数の挿入）を探しています。次に、文字列を取得するときに、指定された文字列の循環文字列が構造に含まれているかどうかを確認します。

入力文字列をTrieに格納することを考えましたが、取得した文字列の循環文字列がTrieに挿入されたかどうかを判断しようとすると、|s|を実行します。Trieで、考えられるすべての循環文字列を検索します。

場所の複雑さがトライのようになる一方で、それをより効率的に行う方法はありますか？

注：文字列の循環文字列とは、たとえば次のすべての循環文字列を意味します1011。0111, 1110, 1101, 1011

4

2 に答える 2

6

以下に基づいて、循環文字列の正規化関数を考え出すことができますか?

  1. ゼロの最大の連続を見つけます。
  2. 一連のゼロが先頭になるように文字列を回転させます。
  3. 同じサイズのゼロの実行ごとに、それを前に回転させると、辞書編集的に少ない文字列が生成されるかどうかを確認し、そうであればそれを使用します。

これにより、等価クラス (1011、1101、1110、0111) のすべてが、辞書編集的に最小の値である 0111 に正規化されます。

0101010101このアルゴリズムがうまく機能しないとげのあるインスタンスですが、ビットが大まかにランダムに分散されている場合、実際には長い文字列に対してうまく機能するはずです。

次に、標準形式に基づいてハッシュするか、空の文字列と 0 で始まる文字列のみを含むトライを使用して、1 回のトライ実行で質問に答えることができます。

編集：

長さ |s| の文字列がある場合 辞書編集的に最小の値を見つけるには多くの時間がかかる場合があります..実際にかかる時間はどれくらいですか?

だから私は010101....それがうまく機能しない値だと言いました. 文字列の長さが n で、最長の 1 の連続の長さが r であるとします。ビットがランダムに分布している場合、 「最長ランの分布」によると、最長ランの長さは O(log n)です。

最長ランを見つける時間は O(n) です。バッファコピーの代わりにオフセットを使用してシフトを実装できます。これは O(1) である必要があります。実行回数は、最悪の場合の O(n / m) です。

次に、ステップ 3 を実行する時間は次のようになります。

  1. 他のロングランを見つける: O(log n) ストレージ平均ケース、O(n) ワーストケースの 1 つの O(n) パス
  2. 各実行: O(log n) 平均ケース、O(n) 最悪ケース
  3.   辞書式にシフトして比較します。ランダムに選択された文字列のほとんどの比較は早期に失敗するため、O(log n) 平均ケース、O(n) 最悪ケースです。

これにより、最悪の場合は O(n²) になりますが、平均的な場合は O(n + log² n) ≅ O(n) になります。

于 2012-01-20T20:49:19.627 に答える
0

n個の文字列s1..snがあり、文字列tが与えられた場合、tの巡回置換が任意のs1..snの部分文字列であるかどうかを知りたいと思います。そして、文字列をできるだけ効率的に保存する必要があります。私はあなたの質問を正しく理解しましたか？

もしそうなら、これが解決策ですが、実行時間は長くなります：与えられた入力tに対して、t'= concat（t、t）とし、s1..snのすべてのsでt'をチェックして、最長のサブシーケンスかどうかを確認しますt'とsmの少なくとも|t| |si|の場合 = k、| t | = l O（nkl）時間で実行されます。また、s1..snを任意のデータ構造に格納できます。それで十分ですか、それともあなたですか？

于 2012-01-20T21:27:29.300 に答える