Java中查找最长重复字符子串的多种高效算法159

在Java编程中，经常会遇到需要查找字符串中最长重复字符子串的问题。这个问题看似简单，但其解法却可以体现出不同的算法效率和代码优雅程度。本文将深入探讨几种解决这个问题的算法，并提供相应的Java代码实现，帮助读者理解和掌握这些算法的优缺点。

问题描述： 给定一个字符串，找到其中最长的重复字符子串。例如，对于字符串"aabbbccccaaa"，最长的重复字符子串是"cccc"。

方法一：暴力法

最直观的解决方法是暴力法。该方法遍历字符串中的每个字符，然后向后扩展，寻找以该字符开头的最长重复字符子串。这种方法简单易懂，但效率较低，时间复杂度为O(n^2)，其中n是字符串的长度。当字符串很长时，性能会急剧下降。```java
public class LongestRepeatingCharacter {
public static String longestRepeatingCharacterBruteForce(String str) {
if (str == null || ()) {
return "";
}
String longestSubstring = "";
for (int i = 0; i < (); i++) {
char currentChar = (i);
String currentSubstring = "";
for (int j = i; j < (); j++) {
if ((j) == currentChar) {
currentSubstring += currentChar;
} else {
break;
}
}
if (() > ()) {
longestSubstring = currentSubstring;
}
}
return longestSubstring;
}
public static void main(String[] args) {
String str = "aabbbccccaaa";
String result = longestRepeatingCharacterBruteForce(str);
("最长重复字符子串 (暴力法): " + result); // 输出: cccc
}
}
```

方法二：动态规划

动态规划是一种更有效率的方法。我们可以使用一个数组 `dp` 来存储以每个字符结尾的最长重复字符子串的长度。 `dp[i]` 表示以 `str[i]` 结尾的最长重复字符子串的长度。如果 `str[i] == str[i-1]`，则 `dp[i] = dp[i-1] + 1`；否则，`dp[i] = 1`。 通过遍历 `dp` 数组，我们可以找到最长的重复字符子串。```java
public static String longestRepeatingCharacterDP(String str) {
if (str == null || ()) {
return "";
}
int[] dp = new int[()];
dp[0] = 1;
int maxLength = 1;
int start = 0;
for (int i = 1; i < (); i++) {
if ((i) == (i - 1)) {
dp[i] = dp[i - 1] + 1;
if (dp[i] > maxLength) {
maxLength = dp[i];
start = i - maxLength + 1;
}
} else {
dp[i] = 1;
}
}
return (start, start + maxLength);
}
```

动态规划方法的时间复杂度为O(n)，空间复杂度为O(n)。比暴力法效率更高。

方法三：滑动窗口

滑动窗口方法也是一种高效的算法。该方法使用两个指针，`left` 和 `right`，表示窗口的左右边界。窗口初始大小为1，不断向右扩展，直到遇到不同的字符。然后，更新最长重复字符子串的长度，并移动 `left` 指针，继续向右扩展窗口。```java
public static String longestRepeatingCharacterSlidingWindow(String str) {
if (str == null || ()) {
return "";
}
int left = 0;
int right = 0;
int maxLength = 0;
int start = 0;
while (right < ()) {
if (right + 1 < () && (right + 1) == (right)) {
right++;
} else {
if (right - left + 1 > maxLength) {
maxLength = right - left + 1;
start = left;
}
left = right + 1;
right++;
}
}
return (start, start + maxLength);
}
```

滑动窗口方法的时间复杂度为O(n)，空间复杂度为O(1)，效率最高。

总结

本文介绍了三种查找最长重复字符子串的Java算法：暴力法、动态规划和滑动窗口。暴力法简单易懂，但效率最低；动态规划和滑动窗口方法效率更高，其中滑动窗口方法的时间和空间复杂度最佳。选择哪种算法取决于具体的需求和字符串的长度。对于大型字符串，滑动窗口方法是最佳选择。 读者可以根据实际情况选择合适的算法来解决问题。

拓展思考： 可以进一步优化算法，例如处理Unicode字符，或者查找最长重复子串（不限于单个字符的重复）。

2025-06-07

上一篇：Java字符编码详解及字符相加的正确方法

下一篇：Java二维数组详解：深入理解数组嵌套及高效应用