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

尹一南

一、项目背景详细介绍

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

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

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

二、项目需求详细介绍

功能性需求

提供静态方法：

1. public static int booth(String s)

复制代码

输入：非空字符串

1. s

复制代码

；

输出：返回最小表示的起始下标

1. k

复制代码

，使得

1. s[k..]+s[0..k-1]

复制代码

在所有旋转中最小。

性能需求

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

鲁棒性需求

• 支持任意字符（包括 Unicode）；
• 对于全部字符相同的字符串，返回 0；
• 输入
  1. null

  复制代码
  或空串时抛出
  1. IllegalArgumentException

  复制代码
  。

质量需求

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

三、相关技术详细介绍

字符串拼接与索引映射

• 为避免频繁对比环绕下标，可将
  1. s

  复制代码
  与自身拼接成
  1. ss = s + s

  复制代码
  ，长度 2N，比较时只需在
  1. [i, i+N)

  复制代码
  区间内。

双指针策略

• 使用
  1. i

  复制代码
  和
  1. j

  复制代码
  两个起始候选下标，以及一个偏移量
  1. k

  复制代码
  表示当前比较位置，循环推进。

跳跃优化

• 当在比较
  1. ss[i+k]

  复制代码
  与
  1. ss[j+k]

  复制代码
  时，一旦不等，可根据大小关系直接把较小起点后面的整个区间跳过，从而避免重复比较。

时间与空间分析

• 每次跳跃至少进步
  1. k+1

  复制代码
  或跳转一个起点，保证指针移动总和 O(N)。
• 辅助空间只需存放拼接后的字符数组，或直接通过索引映射访问原串。

四、实现思路详细介绍

参数检查

• 若
  1. s == null

  复制代码
  或
  1. s.length() == 0

  复制代码
  ，抛出
  1. IllegalArgumentException

  复制代码
  ；

构造双倍字符串

• 1. String ss = s + s;

  复制代码
  或
  1. char[] ss = new char[2*N]

  复制代码
  并填充；

初始化指针

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

复制代码

循环比较

1. while (i < N && j < N && k < N) {
2. char a = ss[i + k];
3. char b = ss[j + k];
4. if (a == b) {
5. k++;
6. } else if (a > b) {
7. // i 的表示比 j 大，i 跳过这段
8. i = i + k + 1;
9. if (i == j) i++;
10. k = 0;
11. } else {
12. // j 的表示比 i 大，j 跳过
13. j = j + k + 1;
14. if (i == j) j++;
15. k = 0;
16. }
17. }
18. return Math.min(i, j);

复制代码

• 每次失配时，将落后者起点向前跳过已比较过的区间，然后重置
  1. k

  复制代码
  ；
• 循环结束后，
  1. min(i, j)

  复制代码
  即为最小旋转起点。

返回结果

• 直接返回起点下标，可用于通过
  1. s.substring(k) + s.substring(0, k)

  复制代码
  构造最小旋转串。

五、完整实现代码

1. // 文件：src/main/java/com/example/string/Booth.java
2. package com.example.string;
4. /**
5. * Booth 算法：在线性时间内求取循环字符串的字典序最小旋转起始下标
6. */
7. public class Booth {
9. /**
10. * 求字符串 s 的最小旋转起始下标
11. * @param s 非空字符串
12. * @return 起始下标 k，使得从 k 开始的旋转最小
13. * @throws IllegalArgumentException 当 s 为 null 或长度为 0 时
14. */
15. public static int booth(String s) {
16. if (s == null || s.length() == 0) {
17. throw new IllegalArgumentException("输入字符串不能为空");
18. }
19. int n = s.length();
20. // 构造双倍字符数组，避免 substring 操作
21. char[] ss = new char[2 * n];
22. for (int i = 0; i < 2 * n; i++) {
23. ss[i] = s.charAt(i % n);
24. }
26. int i = 0, j = 1, k = 0;
27. while (i < n && j < n && k < n) {
28. char a = ss[i + k];
29. char b = ss[j + k];
30. if (a == b) {
31. k++;
32. } else if (a > b) {
33. // i 对应旋转较大，跳过
34. i = i + k + 1;
35. if (i == j) {
36. i++;
37. }
38. k = 0;
39. } else {
40. // j 对应旋转较大，跳过
41. j = j + k + 1;
42. if (i == j) {
43. j++;
44. }
45. k = 0;
46. }
47. }
48. return Math.min(i, j);
49. }
51. /**
52. * 获取最小旋转后的字符串形式
53. * @param s 原始字符串
54. * @return 最小字典序旋转字符串
55. */
56. public static String minimalRotation(String s) {
57. int k = booth(s);
58. return s.substring(k) + s.substring(0, k);
59. }
61. public static void main(String[] args) {
62. String s = "bbaaccaadd";
63. int k = booth(s);
64. System.out.printf("最小旋转起始下标：%d，最小旋转：%s%n", k, minimalRotation(s));
65. }
66. }

复制代码

1. // 文件：src/test/java/com/example/string/BoothTest.java
2. package com.example.string;
4. import org.junit.jupiter.api.Test;
5. import static org.junit.jupiter.api.Assertions.*;
7. /**
8. * 单元测试：验证 Booth 算法功能
9. */
10. public class BoothTest {
12. @Test
13. public void testSimple() {
14. assertEquals(0, Booth.booth("abc"));
15. assertEquals("abc", Booth.minimalRotation("abc"));
16. }
18. @Test
19. public void testRotate() {
20. String s = "cba";
21. // 旋转后最小为 "acb"，起点为 2
22. assertEquals(2, Booth.booth(s));
23. assertEquals("acb", Booth.minimalRotation(s));
24. }
26. @Test
27. public void testRepeatPattern() {
28. String s = "bbaaccaadd";
29. // 所有旋转："bbaaccaadd","baaccaaddb",... 最小为 "aaccaaddbb"
30. assertEquals("aaccaaddbb", Booth.minimalRotation(s));
31. }
33. @Test
34. public void testAllSame() {
35. assertEquals(0, Booth.booth("aaaaa"));
36. assertEquals("aaaaa", Booth.minimalRotation("aaaaa"));
37. }
39. @Test
40. public void testSingleChar() {
41. assertEquals(0, Booth.booth("z"));
42. assertEquals("z", Booth.minimalRotation("z"));
43. }
45. @Test
46. public void testInvalid() {
47. assertThrows(IllegalArgumentException.class, () -> Booth.booth(""));
48. }
49. }

复制代码

六、代码详细解读

booth 方法：

检查输入有效性；

将原串映射到长度为 2N 的字符数组

1. ss

复制代码

，避免复杂的下标计算；

使用双指针

1. i

复制代码

、

1. j

复制代码

和偏移量

1. k

复制代码

，在

1. while

复制代码

循环中比较

1. ss[i+k]

复制代码

与

1. ss[j+k]

复制代码

：

• 相等时
  1. k++

  复制代码
  ；
• 若
  1. ss[i+k] > ss[j+k]

  复制代码
  ，表示从
  1. i

  复制代码
  起的旋转较大，将
  1. i

  复制代码
  跳过已比较部分；
• 否则跳过
  1. j

  复制代码
  ；
• 每次跳跃后重置
  1. k = 0

  复制代码
  ，并确保
  1. i != j

  复制代码
  ；
• 返回
  1. min(i, j)

  复制代码
  ，即最小旋转起点。

minimalRotation 方法：

调用

1. booth

复制代码

得到起点

1. k

复制代码

，通过两次

1. substring

复制代码

拼接出最终旋转字符串。

Test 类：

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

七、项目详细总结

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

八、项目常见问题及解答

问：为何要构造双倍字符数组？
答：避免在比较时对环绕下标进行复杂的取模计算，简化逻辑且性能更优。

问：i、j、k 指针为何能保证 O(N) 复杂度？
答：每次跳跃要么移动

1. i

复制代码

，要么移动

1. j

复制代码

，且每次移动至少进步

1. k+1

复制代码

，整个过程指针总移动量 ≤ 2N。

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

1. char[]

复制代码

改为

1. int[]

复制代码

存放

1. codePoint

复制代码

，并相应地按 code point 比较。

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

1. min(i,j)

复制代码

后，可继续比较另一个指针是否也等价，或在原串中统计所有相同最小串的起点。

九、扩展方向与性能优化

• 内存优化：不构造双倍数组，比较时通过
  1. (idx % n)

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

以上就是Java实现按字典顺序查找的booth算法的完整代码的详细内容，更多关于Java booth算法的资料请关注晓枫资讯其它相关文章！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

盧俊易

路过，支持一下