[Leetcode][1044. 最长重复子串] 3种方法：从暴力到二分，二分搜索 + 字符串哈希，后缀数组
By Long Luo
Leetcode 1044. 最长重复子串 题目如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
191044. 最长重复子串
给你一个字符串s，考虑其所有重复子串：即，s的连续子串，在s中出现2次或更多次。这些出现之间可能存在重叠。
返回**任意一个**可能具有最长长度的重复子串。如果s不含重复子串，那么答案为""。
示例 1：
输入：s = "banana"
输出："ana"
示例 2：
输入：s = "abcd"
输出：""
提示：
2 <= s.length <= 3 * 10^4
s由小写英文字母组成
这是一道Hard难度的题，我们将展示这道题的几种解决方法：
方法一：从暴力到二分
思路与算法：
首先想到的是暴力法，用一个哈希表存储每个字母的出现次数，那么答案字符串的首字母至少出现 \(2\) 次，中间字符至少出现一次。
- 第一层循环 \(0 < i < len - 1\)，遍历整个字符串；
- 第二层循环，子字符串长度，\(i < j < len - i\)；
- 第三层循环，判断第二层循环的字符串在后续字符串中是否出现。
于是写出了下列Ver 1的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36public String longestDupSubstring(String s) {
if (s == null || s.length() <= 1) {
return "";
}
Map<Character, Integer> freq = new HashMap<>();
for (char ch : s.toCharArray()) {
freq.put(ch, freq.getOrDefault(ch, 0) + 1);
}
StringBuilder sb = new StringBuilder();
int len = s.length();
int maxLen = 0;
String ans = "";
for (int i = 0; i < len; i++) {
sb.delete(0, sb.length());
char ch = s.charAt(i);
if (freq.getOrDefault(ch, 0) <= 1) {
continue;
}
for (int j = i; j < len - sb.length(); j++) {
sb.append(s.charAt(j));
for (int k = i + 1; k < len; k++) {
String str = s.substring(k, len);
if (str.contains(sb.toString())) {
if (sb.length() >= maxLen) {
ans = sb.toString();
}
maxLen = Math.max(maxLen, sb.length());
break;
}
}
}
}
return ans;
}
上述代码，时间复杂度为 \(O(n^4)\)，会超时。
通过观察，发现Ver 1代码有很多改进地方，于是更新到Ver 2：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32// BF Opt time: O(n^3) space: O(n)
// Timeout
public static String longestDupSubstring_bf_opt(String s) {
int len = s.length();
int[] cnt = new int[26];
for (char ch : s.toCharArray()) {
cnt[ch - 'a']++;
}
int maxLen = 0;
String ans = "";
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len - 1; i++) {
char ch = s.charAt(i);
if (cnt[ch - 'a'] <= 1) {
continue;
}
for (int segLen = len - i; segLen > maxLen; segLen--) {
sb.delete(0, sb.length());
sb.append(s, i, i + segLen);
String str = s.substring(i + 1, len);
if (str.contains(sb.toString()) && sb.length() > maxLen) {
ans = sb.toString();
maxLen = Math.max(maxLen, sb.length());
break;
}
}
}
return ans;
}
Ver 2时间复杂度降低到 \(O(n^3)\)，但仍然会超时，所以还需要优化！
很明显，题目要求的子字符串的长度范围为 \([0, n - 1]\)，那么枚举每个位置作为起点，二分搜索以找到最大长度，于是有了下面的Ver 3代码：