Minimal Cyclic String Rotation

Worked Example

Consider the word aaba. We double it to aabaaaba to simulate cyclic rotations without modular arithmetic. The distinct rotations are:

1. aaba (start index 0)
2. abaa (start index 1)
3. baaa (start index 2)
4. aaab (start index 3)

Comparing these lexicographically: aaab < aaba < abaa < baaa.

The minimal rotation is aaab starting at index 3.

Experiment

In the interactive module (available at https://riano.app/module/minimal-cyclic-string-rotation), you can experiment with the algorithm:

1. Select different preset words from the "Word preset" dropdown control.
2. Observe the visualizer as it displays the doubled string and highlights the starting index (denoted as k).
3. Test words with varying periodicity to see how the algorithm successfully eliminates inferior candidates.

Limitations

The original Booth algorithm published in 1980 contained a shortcut j - k >= n that could prematurely terminate and return an incorrect answer. Later errata by Booth corrected the condition to j - k > n, although the algorithm runs optimally even with the shortcut entirely removed. Additionally, this module focuses strictly on finite, lowercase ASCII strings within memory limits, and the interactive viewer requires the string to be small enough to render readably.

References

The algorithm and errata are thoroughly documented by its author.

• Booth, K.S. (1980). Lexicographically least circular substrings (with errata discussion).