Circular Buffer Comparison / Lookup Algorithm

Question

I want to detect if a circular buffer is a mirror, or rotation, of a list of other buffers, of the same length.

For example given the following 3 buffers:

AAABCCCA
AABCCBAA
AAAACCAA

Then: CCBAAAAC would match, as it is a mirrored rotation of the first buffer.

Currently I simply compare every buffer in every rotation, then reverse the buffer and do it all again.

This requires: 2*n*i buffer comparisons. (Where n is number of buffers to compare two, and i is the length of the buffer).

Does anyone know a faster algorithm?

The list to compare against grows (as I find one not in the list I had it). Is there a method where I can somehow 'order' buffers, so that comparisons can be done faster?

One idea I had was to also store a sorted version of each buffer, so that you can quickly compare if the same number of items exist.

But is there are more general solution to somehow order by 'circular sequence'?

Answer 1

For each buffer, you could rotate it until it has the minimum lexicographical value.

For example, your example buffers could be rotated like this:

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

This basically means putting the lowest-valued item first. If there is a tie, compare the next items, etc. This gives a unique ordering for any pattern.