Assigning a unique representation to equivalent circular queues

First, a few vague definitions:

Circular queues (or circular buffers) are data structures like normal queues but with their ends connected together (forming a "circle").
wikipedia

Let's say that 2 circular queues are equal if they have the exact same elements in them and the order of items in them are exactly the same.

Example: if we form a circular queue from the string "absa" and one from "bsaa", the two will be equivalent.

My task is to group together "cyclic equivalent" strings. I'm trying to find a "base representation" for all "cyclic equivalent" strings to use it as an "index" in a hash table which would make grouping them more efficient.

Help me find an algorithm that can assign a single unique representation to all equal circular queues!

• is it even possible? (let alone useful?)

• what about problematic ones like "asdasd"? (see balanced bike wheel analogy)

Some ideas to base the algorithm on:

• bicycle wheel analogy: Imagine your bike's wheels have colored spokes, all kinds of colors, each color having a different weight (terrible idea for everyone except for computer scientists). If you flip your bike upside down letting the wheel spin freely, the part of the wheel with the most torque will rotate to the bottom and the wheel will stay in that "base position" and that bottom point of the wheel could be called its "base index". If we recorded the order of the colored spokes starting at that point, that order could be called a linear "base representation" of the wheel. This would not happen in the case of a properly balanced wheel, which would not start rotating. What could we do in that case?

• ?

Some practical use cases:

• finding equivalent circular transportation routes on a map (like those of public transportation) regardless of starting and ending point

• ?

Enumerate all possible rotations of the queue. Take the lexicographically first of them. Use this as your representative. If you want a short index into a hash table, take the hash of that. Then any two equivalent queues will get the same representative / same index.

If the queue has $n$ items, implementing this naively takes $O(n^2)$ time. However, it can be done more efficiently. When the contents of the queue are random, sorting the rotations lexicographically, using a string comparison operator that only compares as much of a prefix as necessary to find the first mismatch, will have running time $O(n \log^2 n)$. If you want to get more fancy, you can do it in $O(n)$ time, using a suffix tree or suffix array; though the constant factors and implementation complexity probably won't make this worthwhile unless your queues are extremely large.

StackExchange Computer Science Q#65583, answer score: 11