public static int booth(String s)

int i = 0, j = 1, k = 0, N = s.length();

while (i < N && j < N && k < N) {
    char a = ss[i + k];
    char b = ss[j + k];
    if (a == b) {
        k++;
    } else if (a > b) {
        // i 的表示比 j 大，i 跳過這段
        i = i + k + 1;
        if (i == j) i++;
        k = 0;
    } else {
        // j 的表示比 i 大，j 跳過
        j = j + k + 1;
        if (i == j) j++;
        k = 0;
    }
}
return Math.min(i, j);

// 文件：src/main/java/com/example/string/Booth.java
package com.example.string;
 
/**
 * Booth 算法：在線性時(shí)間內(nèi)求取循環(huán)字符串的字典序最小旋轉(zhuǎn)起始下標(biāo)
 */
public class Booth {
 
    /**
     * 求字符串 s 的最小旋轉(zhuǎn)起始下標(biāo)
     * @param s 非空字符串
     * @return 起始下標(biāo) k，使得從 k 開始的旋轉(zhuǎn)最小
     * @throws IllegalArgumentException 當(dāng) s 為 null 或長度為 0 時(shí)
     */
    public static int booth(String s) {
        if (s == null || s.length() == 0) {
            throw new IllegalArgumentException("輸入字符串不能為空");
        }
        int n = s.length();
        // 構(gòu)造雙倍字符數(shù)組，避免 substring 操作
        char[] ss = new char[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            ss[i] = s.charAt(i % n);
        }
 
        int i = 0, j = 1, k = 0;
        while (i < n && j < n && k < n) {
            char a = ss[i + k];
            char b = ss[j + k];
            if (a == b) {
                k++;
            } else if (a > b) {
                // i 對應(yīng)旋轉(zhuǎn)較大，跳過
                i = i + k + 1;
                if (i == j) {
                    i++;
                }
                k = 0;
            } else {
                // j 對應(yīng)旋轉(zhuǎn)較大，跳過
                j = j + k + 1;
                if (i == j) {
                    j++;
                }
                k = 0;
            }
        }
        return Math.min(i, j);
    }
 
    /**
     * 獲取最小旋轉(zhuǎn)后的字符串形式
     * @param s 原始字符串
     * @return 最小字典序旋轉(zhuǎn)字符串
     */
    public static String minimalRotation(String s) {
        int k = booth(s);
        return s.substring(k) + s.substring(0, k);
    }
 
    public static void main(String[] args) {
        String s = "bbaaccaadd";
        int k = booth(s);
        System.out.printf("最小旋轉(zhuǎn)起始下標(biāo)：%d，最小旋轉(zhuǎn)：%s%n", k, minimalRotation(s));
    }
}

// 文件：src/test/java/com/example/string/BoothTest.java
package com.example.string;
 
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
 
/**
 * 單元測試：驗(yàn)證 Booth 算法功能
 */
public class BoothTest {
 
    @Test
    public void testSimple() {
        assertEquals(0, Booth.booth("abc"));
        assertEquals("abc", Booth.minimalRotation("abc"));
    }
 
    @Test
    public void testRotate() {
        String s = "cba";
        // 旋轉(zhuǎn)后最小為 "acb"，起點(diǎn)為 2
        assertEquals(2, Booth.booth(s));
        assertEquals("acb", Booth.minimalRotation(s));
    }
 
    @Test
    public void testRepeatPattern() {
        String s = "bbaaccaadd";
        // 所有旋轉(zhuǎn)："bbaaccaadd","baaccaaddb",... 最小為 "aaccaaddbb"
        assertEquals("aaccaaddbb", Booth.minimalRotation(s));
    }
 
    @Test
    public void testAllSame() {
        assertEquals(0, Booth.booth("aaaaa"));
        assertEquals("aaaaa", Booth.minimalRotation("aaaaa"));
    }
 
    @Test
    public void testSingleChar() {
        assertEquals(0, Booth.booth("z"));
        assertEquals("z", Booth.minimalRotation("z"));
    }
 
    @Test
    public void testInvalid() {
        assertThrows(IllegalArgumentException.class, () -> Booth.booth(""));
    }
}