一、項(xiàng)目背景詳細(xì)介紹

在字符串算法領(lǐng)域，“最小表示法”是一種用于求取一個(gè)環(huán)形字符串（或循環(huán)右移后形成的新串）中字典序最小的排列位置的經(jīng)典問題。它在字符串匹配、環(huán)形模式檢測(cè)、基因序列比對(duì)、字符串哈希與壓縮等場(chǎng)景均有重要應(yīng)用。

樸素做法需要枚舉所有 N 個(gè)旋轉(zhuǎn)，分別比較長(zhǎng)度為 N 的字符串，時(shí)間復(fù)雜度 O(N²)，對(duì)大規(guī)模文本不具備實(shí)用性。Booth 算法利用雙指針與跳躍策略，將求最小表示的時(shí)間復(fù)雜度降到 O(N)，且只需常量級(jí)額外空間，極大地提升了性能。

本項(xiàng)目將基于 Java 完整實(shí)現(xiàn) Booth 算法，幫助讀者深入理解算法原理，學(xué)會(huì)在工程中高效地對(duì)循環(huán)字符串進(jìn)行字典序比較，并掌握相關(guān)代碼優(yōu)化和邊界處理技巧。

二、項(xiàng)目需求詳細(xì)介紹

功能性需求

提供靜態(tài)方法：

public static int booth(String s)

輸入：非空字符串 s；

輸出：返回最小表示的起始下標(biāo) k，使得 s[k..]+s[0..k-1] 在所有旋轉(zhuǎn)中最小。

性能需求

• 時(shí)間復(fù)雜度：O(N)，其中 N 為字符串長(zhǎng)度；
• 空間復(fù)雜度：O(1) 或 O(N)（若需要構(gòu)造雙倍字符串輔助比較）。

魯棒性需求

• 支持任意字符（包括 Unicode）；
• 對(duì)于全部字符相同的字符串，返回 0；
• 輸入 null 或空串時(shí)拋出 IllegalArgumentException。

質(zhì)量需求

• 代碼注釋清晰、邏輯分明；
• 單元測(cè)試覆蓋正常場(chǎng)景、邊界場(chǎng)景（如全部相同、長(zhǎng)度為 1、含重復(fù)模式）；
• 使用 Maven 管理，集成 CI 運(yùn)行測(cè)試。

三、相關(guān)技術(shù)詳細(xì)介紹

字符串拼接與索引映射

• 為避免頻繁對(duì)比環(huán)繞下標(biāo)，可將 s 與自身拼接成 ss = s + s，長(zhǎng)度 2N，比較時(shí)只需在 [i, i+N) 區(qū)間內(nèi)。

雙指針策略

• 使用 i 和 j 兩個(gè)起始候選下標(biāo)，以及一個(gè)偏移量 k 表示當(dāng)前比較位置，循環(huán)推進(jìn)。

跳躍優(yōu)化

• 當(dāng)在比較 ss[i+k] 與 ss[j+k] 時(shí)，一旦不等，可根據(jù)大小關(guān)系直接把較小起點(diǎn)后面的整個(gè)區(qū)間跳過，從而避免重復(fù)比較。

時(shí)間與空間分析

• 每次跳躍至少進(jìn)步 k+1 或跳轉(zhuǎn)一個(gè)起點(diǎn)，保證指針移動(dòng)總和 O(N)。
• 輔助空間只需存放拼接后的字符數(shù)組，或直接通過索引映射訪問原串。

四、實(shí)現(xiàn)思路詳細(xì)介紹

參數(shù)檢查

• 若 s == null 或 s.length() == 0，拋出 IllegalArgumentException；

構(gòu)造雙倍字符串

• String ss = s + s; 或 char[] ss = new char[2*N] 并填充；

初始化指針

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

循環(huán)比較

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);

• 每次失配時(shí)，將落后者起點(diǎn)向前跳過已比較過的區(qū)間，然后重置 k；
• 循環(huán)結(jié)束后，min(i, j) 即為最小旋轉(zhuǎn)起點(diǎn)。

返回結(jié)果

• 直接返回起點(diǎn)下標(biāo)，可用于通過 s.substring(k) + s.substring(0, k) 構(gòu)造最小旋轉(zhuǎn)串。

五、完整實(shí)現(xiàn)代碼

// 文件：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 或長(zhǎng)度為 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 對(duì)應(yīng)旋轉(zhuǎn)較大，跳過
                i = i + k + 1;
                if (i == j) {
                    i++;
                }
                k = 0;
            } else {
                // j 對(duì)應(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.*;
 
/**
 * 單元測(cè)試：驗(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(""));
    }
}

六、代碼詳細(xì)解讀

booth 方法：

檢查輸入有效性；

將原串映射到長(zhǎng)度為 2N 的字符數(shù)組 ss，避免復(fù)雜的下標(biāo)計(jì)算；

使用雙指針 i、j 和偏移量 k，在 while 循環(huán)中比較 ss[i+k] 與 ss[j+k]：

• 相等時(shí) k++；
• 若 ss[i+k] > ss[j+k]，表示從 i 起的旋轉(zhuǎn)較大，將 i 跳過已比較部分；
• 否則跳過 j；
• 每次跳躍后重置 k = 0，并確保 i != j；
• 返回 min(i, j)，即最小旋轉(zhuǎn)起點(diǎn)。

minimalRotation 方法：

調(diào)用 booth 得到起點(diǎn) k，通過兩次 substring 拼接出最終旋轉(zhuǎn)字符串。

Test 類：

覆蓋基本無旋轉(zhuǎn)、單字符、全相同、普通旋轉(zhuǎn)、重復(fù)模式、非法輸入等場(chǎng)景，確保算法正確與魯棒。

七、項(xiàng)目詳細(xì)總結(jié)

通過本項(xiàng)目，您深入掌握了 Booth 算法在 Java 中的端到端實(shí)現(xiàn)：從理論推導(dǎo)、邊界分析，到代碼優(yōu)化與單元測(cè)試，全面覆蓋常見使用場(chǎng)景。Booth 算法能在線性時(shí)間內(nèi)解決循環(huán)字符串的最小字典序問題，對(duì)于大規(guī)模文本和高性能要求的系統(tǒng)具有重要實(shí)用價(jià)值。

八、項(xiàng)目常見問題及解答

問：為何要構(gòu)造雙倍字符數(shù)組？
答：避免在比較時(shí)對(duì)環(huán)繞下標(biāo)進(jìn)行復(fù)雜的取模計(jì)算，簡(jiǎn)化邏輯且性能更優(yōu)。

問：i、j、k 指針為何能保證 O(N) 復(fù)雜度？
答：每次跳躍要么移動(dòng) i，要么移動(dòng) j，且每次移動(dòng)至少進(jìn)步 k+1，整個(gè)過程指針總移動(dòng)量 ≤ 2N。

問：如何支持 Unicode 超出 BMP 的字符？
答：可將 char[] 改為 int[] 存放 codePoint，并相應(yīng)地按 code point 比較。

問：如何改造為返回所有最小旋轉(zhuǎn)起點(diǎn)？
答：在找到 min(i,j) 后，可繼續(xù)比較另一個(gè)指針是否也等價(jià)，或在原串中統(tǒng)計(jì)所有相同最小串的起點(diǎn)。

九、擴(kuò)展方向與性能優(yōu)化

• 內(nèi)存優(yōu)化：不構(gòu)造雙倍數(shù)組，比較時(shí)通過 (idx % n) 取模訪問原串，同時(shí)通過局部變量緩存長(zhǎng)度減少重復(fù)成員訪問。
• 并行預(yù)處理：在超長(zhǎng)串中，可分段并行計(jì)算局部最小旋轉(zhuǎn)，再在小規(guī)模結(jié)果中二次比較得全局最小。
• GPU 加速：對(duì)于海量基因序列，可將字符比較并行映射到 GPU 核心，加速大批量最小旋轉(zhuǎn)計(jì)算。
• 泛型支持：改造算法以支持任意可比對(duì)象數(shù)組的循環(huán)最小表示，應(yīng)用于環(huán)形圖像或環(huán)狀數(shù)據(jù)結(jié)構(gòu)比對(duì)。
• 與最小表達(dá)式結(jié)合：將 Booth 算法與壓縮算法結(jié)合，生成循環(huán)最小表示再做后續(xù)哈?；蜃值渌饕嵘臋z索性能。

以上就是Java實(shí)現(xiàn)按字典順序查找的booth算法的完整代碼的詳細(xì)內(nèi)容，更多關(guān)于Java booth算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論