/** * This file contains an implementation of Booths algorithms which * finds the lexicographically smallest string rotation. **/ public class BoothsAlgorithm { // Performs Booths algorithm returning the earliest index of the // lexicographically smallest string rotation. Note that comparisons // are done using ASCII values, so mixing lowercase and uppercase // letters may give you unexpected results, O(n) public static int leastCyclicRotation(String s) { s += s; int[] f = new int[s.length()]; java.util.Arrays.fill(f, -1); int k = 0; for (int j=1; j < s.length(); j++) { char sj = s.charAt(j); int i = f[j-k-1]; while (i != -1 && sj != s.charAt(k+i+1)) { if (sj < s.charAt(k+i+1)) k = j-i-1; i = f[i]; } if (sj != s.charAt(k+i+1)) { if (sj < s.charAt(k)) k = j; f[j-k] = -1; } else f[j-k] = i + 1; } return k; } public static void main(String[] args) { String s = "abcde"; int index = leastCyclicRotation(s); // Outputs 0 since the string is already in its least rotation System.out.println(index); s = "cdeab"; index = leastCyclicRotation(s); // Outputs 3 since rotating the string 3 times to the left makes // the smallest rotation: "cdeab" -> "deabc" -> "eabcd" -> "abcde" System.out.println(index); } }