How to Learn Booth’s Algorithm: String Rotations, Failure Functions, Candidate Elimination and Linear-Time Lexicographic Minimisation

Wait, What?

A circular string has no obvious beginning—so the algorithm’s job is to choose one canonically.

Booth’s algorithm finds the lexicographically smallest rotation of a string in linear time. The problem sounds narrow until you notice what it teaches: circular data, canonical representation, prefix-failure logic, candidate elimination, careful indexing and the difference between comparing every possibility and proving that whole groups of possibilities can be discarded at once.

For a beginner, the entry point is simply rotating a word and comparing the results. For an intermediate learner, the challenge is to see how repeated comparisons can be reused. At advanced level, the algorithm becomes a lesson in invariants and amortised reasoning. At professional level, you must also handle repeated periods, Unicode, empty input, deterministic canonicalisation and the choice between Booth, Duval and other minimal-rotation methods.

Quick Answer

Learn Booth’s algorithm in this order: circular rotations → lexicographic order → naive O(n²) comparison → doubled-string view → shared prefixes → failure-function intuition → candidate start index → elimination rule → linear-time argument → periodic strings → canonicalisation → production testing.

1. Start with all rotations

Take:

baca

Its rotations are:

baca
acab
caba
abac

The lexicographically smallest is abac, starting at index 3.

A beginner should be able to generate every rotation and choose the smallest one before learning any optimisation. This gives a transparent correctness oracle for later testing.

2. Why the naive method becomes expensive

There are n possible starting positions. Comparing two rotations can inspect up to n characters. The obvious method is therefore quadratic in the worst case.

Strings with long repeated prefixes are especially unfriendly because many comparisons run for a long time before finding a difference.

3. The circular-string trick: look at s+s

Every rotation of a string s of length n appears as a length-n substring of s+s.

For baca:

bacabaca

The rotation beginning at index 3 is the length-four slice starting there.

This trick removes much of the mental burden of modular wrap-around, although implementations may still use modulo indexing to avoid materialising a second copy.

4. Booth’s central idea: failed comparisons contain information

Suppose candidate start k matches another start for several characters and then loses because its next differing character is larger.

The important observation is that some starts inside that matched region cannot suddenly become the minimum. The comparison that defeated k gives enough structure to skip candidates rather than testing them independently.

This is the same broad algorithmic habit seen in KMP: a mismatch is not merely failure. It tells you how much previously matched structure can still be trusted.

5. Why the failure function appears

Booth’s 1980 method is built from a modified Knuth–Morris–Pratt-style failure function. The failure structure records border information—how much of a prefix remains useful after a mismatch.

For teaching, do not begin by memorising the array update. First ask:

What prefix have we already established?
When two candidate rotations disagree, which candidate is definitely worse?
How far can we move without rechecking comparisons that have already been explained?

Once those questions are clear, the failure array becomes bookkeeping rather than magic.

6. A language-neutral sketch

n = length(s)
if n == 0:
    return 0

failure = array(2*n, -1)
k = 0

for j from 1 to 2*n-1:
    i = failure[j-k-1]

    while i != -1 and s[j mod n] != s[(k+i+1) mod n]:
        if s[j mod n] < s[(k+i+1) mod n]:
            k = j-i-1
        i = failure[i]

    if i == -1 and s[j mod n] != s[(k+i+1) mod n]:
        if s[j mod n] < s[(k+i+1) mod n]:
            k = j
        failure[j-k] = -1
    else:
        failure[j-k] = i+1

return k mod n

This is compact code, but compactness is not understanding. The learner should be able to explain what k means at every stage: it is the best surviving candidate start known so far.

7. The invariant that makes the algorithm learnable

A useful learning invariant is:

Every starting position before the current surviving candidate that has been eliminated has a witnessed reason it cannot produce a lexicographically smaller rotation.

That sentence is more valuable than remembering the loop. It tells you why skipping work does not sacrifice correctness.

8. Linear time is not “because there is one loop”

The code contains fallback steps, so a superficial loop count can be misleading. The linear bound comes from controlled progress: candidate positions move forward, and failure links prevent the same comparisons from being rediscovered without limit.

As with KMP, the right question is not “how many nested loops are visible?” but “how many times can the indices move in each direction over the whole execution?”

9. Periodic strings are the real test

Consider:

ababab

Several rotations are identical. A correct implementation must return a valid minimal starting index without assuming the minimum is unique.

Periodic strings are excellent tests because they exercise long equality runs, wrap-around and failure-function behaviour simultaneously.

10. Canonicalisation is the deeper application

Suppose two objects are represented by circular sequences, but the chosen starting point is arbitrary. If both are rotated to their lexicographically minimal form, they gain a canonical representation.

Then equality testing can become:

canonical(a) == canonical(b)

This pattern appears in problems involving cyclic strings and in broader canonisation tasks where equivalent objects need one deterministic representation.

11. Canonical does not mean semantically complete

Choosing a minimal rotation only removes rotational ambiguity. It does not automatically remove reflection, renaming, reversal or other equivalences your domain may care about.

Professional modelling begins by defining the exact equivalence relation. Booth solves one part: cyclic shift.

12. Unicode changes what “character” means

The algorithm assumes an ordered alphabet of symbols. In software, that raises questions:

Are symbols bytes?
Unicode code points?
Grapheme clusters?
Case-folded and normalised text?

Lexicographic order over bytes may not match user-visible alphabetical order. A technically correct Booth implementation can therefore produce an inappropriate canonical form if the symbol model is wrong.

13. Begin with a quadratic oracle

Keep the naive algorithm:

best = 0
for start in 1..n-1:
    if rotation(start) < rotation(best):
        best = start

Use it on small random strings and compare its answer to Booth’s result. When multiple minimal rotations are equal, compare the resulting rotated strings rather than requiring the same index.

This is one of the cleanest ways to validate a subtle string algorithm.

14. A tracing exercise that exposes the logic

For a short string, record:

j | current candidate k | fallback i | compared symbols | decision

Before each update, ask the learner to predict whether the current candidate survives.

Programming-education evidence on code tracing, worked examples and PRIMM-style prediction supports this approach: reading and explaining state changes should come before unsupported implementation.

15. Compare Booth with Duval

Duval’s algorithm uses Lyndon factorisation and can also solve minimal rotation in linear time with constant extra space in common formulations. Booth and Duval therefore make a useful comparative study.

Ask:

Which invariant is easier to explain?
Which implementation is easier to audit?
What extra memory is used?
Which version already exists in the codebase?
Does the workload need only minimal rotation or Lyndon factorisation too?

Professional algorithm choice is often about maintainability and adjacent needs, not asymptotic notation alone.

16. Failure modes worth forcing

empty string;
one symbol;
all symbols identical;
already minimal string;
strictly descending symbols;
highly periodic strings;
two or more equal minimal rotations;
non-ASCII input;
very long common prefixes;
off-by-one errors at 2n boundaries.

17. Beginner-to-professional learning ladder

Beginner: list every rotation of a short string and select the minimum.
Foundation: implement the quadratic oracle and explain doubled-string indexing.
Intermediate: trace Booth’s candidate and failure states by hand.
Advanced: explain the elimination invariant and the linear-time argument.
Professional: validate against the oracle, define symbol normalisation, compare Booth with Duval and document the equivalence relation being canonicalised.

18. Ownership boundary

This article owns Booth’s algorithm as a learning object: lexicographically minimal circular rotation, failure-function reuse, candidate elimination, linear-time reasoning and canonicalisation trade-offs. It does not replace the broader string-algorithms estate, KMP, suffix structures, general parsing, learner measurement, MindOS, Bolt or Student/Studying Interface canonical jobs.

Sources and further reading

Kellogg S. Booth, “Lexicographically Least Circular Substrings,” Information Processing Letters 10(4–5), 1980: DOI 10.1016/0020-0190(80)90149-0.
Kellogg S. Booth’s University of British Columbia publication page: Lexicographically least circular substrings.
Qisheng Wang and Mingsheng Ying, modern overview of lexicographically minimal string rotation and classical linear-time algorithms: Theory of Computing Systems.
Sue Sentance, Jane Waite and Maria Kallia, PRIMM programming-education research: SIGCSE 2019.
Matthew Hassan et al., research on novice code tracing: SIGCSE 2022.

Professional rule: you understand Booth’s algorithm when you can explain why a mismatch eliminates candidate starts, not just reproduce the failure-array code, and when you can state exactly what equivalence your canonical rotation is supposed to remove.

Small Group Tutorials