2

循環バッファーが、同じ長さの他のバッファーのリストのミラーまたは回転であるかどうかを検出したいと考えています。

たとえば、次の 3 つのバッファがあるとします。

AAABCCCA
AABCCBAA
AAAACCAA

Then: CCBAAAAC最初のバッファーのミラーリングされたローテーションであるため、一致します。

現在、ローテーションごとにすべてのバッファを比較し、バッファを逆にしてすべてをやり直しています。

これには以下が必要です: 2*n*iバッファ比較。(n は 2 つを比較するバッファーの数、i はバッファーの長さ)。

より高速なアルゴリズムを知っている人はいますか?

比較するリストが大きくなります (私が持っていたリストにないものを見つけたので)。比較をより高速に行えるように、何らかの方法でバッファを「順序付け」できる方法はありますか?

私が思いついたアイデアの 1 つは、同じ数のアイテムが存在するかどうかをすばやく比較できるように、各バッファーの並べ替えられたバージョンも格納することでした。

しかし、どういうわけか「循環シーケンス」で順序付けするためのより一般的な解決策はありますか?

4

1 に答える 1

3

バッファーごとに、辞書編集上の最小値になるまで回転させることができます。

たとえば、サンプル バッファーは次のようにローテーションできます。

AAABCCCA -> AAAABCCC
AABCCBAA -> AAAABCCB
AAAACCAA -> AAAAAACC

これは基本的に、最も価値の低いアイテムを最初に置くことを意味します。同点の場合は、次の項目などを比較します。これにより、任意のパターンに一意の順序が付けられます。

于 2013-06-13T01:31:19.210 に答える