Pattern Reference
String Rotations
"Lexicographically minimal rotation (Booth's), string matching on rotation, periodic strings."
Loading...
Deep Dive Tutorial
Rotation check: A is a rotation of B iff len(A) = len(B) and A is a substring of B+B. O(n) with KMP/hashing. Booth's algorithm: find the starting index of the lexicographically smallest rotation in O(n) using a "canonical rotation" technique. Key insight: maintain a "current best" position and a comparison with a "challenge" position, advancing both along the doubled string.
Booth's algorithm for minimum rotation
// Booth's algorithm: find start index of lexicographically smallest rotation
// Returns index i such that s[i..]+s[..i-1] is the smallest rotation
function boothMinRotation(s) {
const n = s.length;
const t = s + s; // doubled string
const f = new Array(2 * n).fill(-1);
let k = 0; // current best start position
for (let j = 1; j < 2 * n; j++) {
let i = f[j - k - 1];
while (i !== -1 && t[j] !== t[k + i + 1]) {
if (t[j] < t[k + i + 1]) k = j - i - 1;
i = f[i];
}
if (t[j] !== t[k + i + 1]) {
if (t[j] < t[k]) k = j;
f[j - k] = -1;
} else {
f[j - k] = i + 1;
}
}
return k;
}
// Simple check: is B a rotation of A?
function isRotation(A, B) {
return A.length === B.length && (A + A).includes(B);
}
// All rotations of a string
function allRotations(s) {
const doubled = s + s;
return Array.from({length: s.length}, (_, i) => doubled.slice(i, i + s.length));
}Worked Problems
refresh-cw
String rotation techniques:
- Check rotation: B in A+A, O(n) with KMP
- All rotations: doubled string approach, O(n) per rotation
- Minimum rotation: Booth's algorithm O(n)
- Equivalent circular strings: compare canonical (minimum) rotations
Booth's algorithm: Uses a failure function similar to KMP to avoid comparing the same characters repeatedly. The key invariant: k is always the starting position of the current lexicographically smallest rotation candidate.
Applications: Cyclic string equivalence, circular sequence alignment, rotating buffer problems, string period problems (smallest period = smallest rotation that is a rotation of itself).
- Check rotation: B in A+A, O(n) with KMP
- All rotations: doubled string approach, O(n) per rotation
- Minimum rotation: Booth's algorithm O(n)
- Equivalent circular strings: compare canonical (minimum) rotations
Booth's algorithm: Uses a failure function similar to KMP to avoid comparing the same characters repeatedly. The key invariant: k is always the starting position of the current lexicographically smallest rotation candidate.
Applications: Cyclic string equivalence, circular sequence alignment, rotating buffer problems, string period problems (smallest period = smallest rotation that is a rotation of itself).