Java实现按字典顺序查找的booth算法的完整代码

目录

• 一、项目背景详细介绍
• 二、项目需求详细介绍
• 三、相关技术详细介绍
• 四、实现思路详细介绍
• 五、完整实现代码
• 六、代码详细解读
• 七、项目详细总结
• 八、项目常见问题及解答
• 九、扩展方向与性能优化

一、项目背景详细介绍

在字符串算法领域，“最小表示法”是一种用于求取一个环形字符串（或循环右移后形成的新串）中字典序最小的排列位置的经典问题。它在字符串匹配、环形模式检测、基因序列比对、字符串哈希与压缩等场景均有重要应用。

朴素做法需要枚举所有 N 个旋转，分别比较长度为 N 的字符串，时间复杂度 O(N²)，对大规模文本不具备实用性。Booth 算法利用双指针与跳跃策略，将求最小表示的时间复杂度降到 O(N)，且只需常量级额外空间，极大地提升了性能。

本项目将基于 Java 完整实现 Booth 算法，帮助读者深入理解算法原理，学会在工程中高效地对循环字符串进行字典序比较，并掌握相关代码优化和边界处理技巧。

二、项目需求详细介绍

功能性需求

提供静态方法：

public static int booth(String s)

输入：非空字符串 s；

输出：返回最小表示的起始下标 k，使得 s[k..]+s[0..k-1] 在所有旋转中最小。

性能需求

• 时间复杂度：O(N)，其中 N 为字符串长度；
• 空间复杂度：O(1) 或 O(N)（若需要构造双倍字符串辅助比较）。

鲁棒性需求

• 支持任意字符（包括 Unicode）；
• 对于全部字符相同的字符串，返回 0；
• 输入 null 或空串时抛出 IllegalArgumentException。

质量需求

• 代码注释清晰、逻辑分明；
• 单元测试覆盖正常场景、边界场景（如全部相同、长度为 1、含重复模式）；
• 使用 Maven 管理，集成 CI 运行测试。

三、相关技术详细介绍

字符串拼接与索引映射

• 为避免频繁对比环绕下标，可将 s 与自身拼接成 ss = s + s，长度 2N，比较时只需在 [i, i+N) 区间内。

双指针策略

• 使用 i 和 j 两个起始候选下标，以及一个偏移量 k 表示当前比较位置，循环推进。

跳跃优化

• 当在比较 ss[i+k] 与 ss[j+k] 时，一旦不等，可根据大小关系直接把较小起点后面的整个区间跳过，从而避免重复比较。

时间与空间分析

• 每次跳跃至少进步 k+1 或跳转一个起点，保证指针移动总和 O(N)。
• 辅助空间只需存放拼接后的字符数组，或直接通过索引映射访问原串。

四、实现思路详细介绍

参数检查

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

构造双倍字符串

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

初始化指针

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

• 每次失配时，将落后者起点向前跳过已比较过的区间，然后重置 k；
• 循环结束后，min(i, j) 即为最小旋转起点。

返回结果

• 直接返回起点下标，可用于通过 s.substring(k) + s.substring(0, k) 构造最小旋转串。

五、完整实现代码

// 文件：src/main/java/com/example/string/Booth.java
package com.example.string;
 
/**
 * Booth 算法：在线性时间内求取循环字符串的字典序最小旋转起始下标
 */
public class Booth {
 
    /**
     * 求字符串 s 的最小旋转起始下标
     * @param s 非空字符串
     * @return 起始下标 k，使得从 k 开始的旋转最小
     * @throws IllegalArgumentException 当 s 为 null 或长度为 0 时
     */
    public static int booth(String s) {
        if (s == null || s.length() == 0) {
            throw new IllegalArgumentException("输入字符串不能为空");
        }
        int n = s.lwww.devze.comength();
        // 构造双倍字符数组，避免 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 对应旋转较大，跳过
                i = i + k + 1;
                if (i == j) {
                    i++;
                }
                k = 0;
            } else {
                // j 对应旋转较大，跳过
                j = j + k + 1;
                if (i == j) {
                    j++;
                }
                k = 0;
            }
        }
        return Math.min(i, j);
    }
 
    /**
     * 获取最小旋转后的字符串形式
     * @param s 原始字符串
     * @return 最小字典序旋转字符串
     */
    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("最小旋转起始下标：%d，最小旋转：%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.*;
 
/**
 * 单元测试：验证 Boophpth 算法功能
 */
public class BoothTest {
 
    @Test
    public void testSimple() {
        assertEquals(0, Booth.booth("abc"));
        assertEquals("abc", Booth.minimalRotation("abc"));
    }
 
    @Test
    public void testRotate() {
        String s = "cba";
        // 旋转后最小为 "acb"，起点为 2
        assertEquals(2, Booth.bophpoth(s));
        assertEquals("acb", Booth.minimalRotation(s));
    }
 
    @Test
    public void testRepeatPattern() {
        String s = "bbaaccaadd";
        // 所有旋转："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(""));
    }
}

六、代码详细解读

booth 方法：

检查输入有效性；

将原串映射到长度为 2N 的字符数组 ss，避免复杂的下标计算；

使用双指针 i、j 和偏移量 k，在 while 循环中比较 ss[i+k] 与 ss[j+k]：

• 相等时 k++；
• 若 ss[i+k] > ss[j+k]，表示从 i 起的旋转较大，将 i 跳过已比较部分；
• 否则跳过 j；
• 每次跳跃后重置 k = 0，并确保 i != j；
• 返回 min(i, j)，即最小旋转起点。

mifZsFWmryAnimalRotation 方法：

调用 booth 得到起点 k，通过两次 substring 拼接出最终旋转字符串。

Test 类：

覆盖基本无旋转、单字符、全相同、普通旋转、重复模式、非法输入等场景，确保算法正确与鲁棒。

七、项目详细总结

通过本项目，您深入掌握了 Booth 算法在 Java 中的端到端实现：从理论推导、边界分析，到代码优化与单元测试，全面覆盖常见使用场景。Booth 算法能在线性时间内解决循环字符串的最小字典序问题，对于大规模文本和高性能要求的系统具有重要实用价值。

八、项目常见问题及解答

问：为何要构造双倍字符数组？

答：避免在比较时对环绕下标进行复杂的取模计算，简化逻辑且性能更优。

问：i、j、k 指针为何能保证 O(N) 复杂度？

答：每次跳跃要么移动 i，要么移动 j，且每次移动至少进步 k+1，整个过程指针总移动量 ≤ 2N。

问：如何支持 Unicode 超出 BMP 的字符？

答：可将 char[] 改为 int[] 存放 codePoint，并相应地按 code point 比较。

问：如何改造为返回所有最小旋转起点？

答：在找到 min(i,j) 后，可继续比较另一个指针是否也等价，或在原串中统计所有相同最小串的起点。

九、扩展方向与性能优化

• 内存优化：不构造双编程倍数组，比较时通过 (idx % n) 取模访问原串，同时通过局部变量缓存长度减少重复成员访问。
• 并行预处理：在超长串中，可分段并行计算局部最小旋转，再在小规模结果中二次比较得全局最小。
• GPU 加速：对于海量基因序列，可将字符比较并行映射到 GPU 核心，加速大批量最小旋转计算。
• 泛型支持：改造算法以支持任意可比对象数组的循环最小表示，应用于环形图像或环状数据结构比对。
• 与最小表达式结合：将 Booth 算法与压缩算法结合，生成循环最小表示再做后续哈希或字典索引，提升全文检索性能。

以上就是Java实现按字典顺序查找的booth算法的完整代码的详细内容，更多关于Java booth算法的资料请关注编程客栈(www.devze.com)其它相关文章！