[Leetcode][1044. 最长重复子串] 3种方法：从暴力到二分，二分搜索 + 字符串哈希，后缀数组

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4.4k 阅读时长 ≈ 4 分钟

By Long Luo

Leetcode 1044. 最长重复子串 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1044. 最长重复子串

给你一个字符串s，考虑其所有重复子串：即，s的连续子串，在s中出现2次或更多次。这些出现之间可能存在重叠。

返回**任意一个**可能具有最长长度的重复子串。如果s不含重复子串，那么答案为""。


示例 1：
输入：s = "banana"
输出："ana"

示例 2：
输入：s = "abcd"
输出：""
 

提示：
2 <= s.length <= 3 * 10^4
s由小写英文字母组成

这是一道Hard难度的题，我们将展示这道题的几种解决方法：

方法一：从暴力到二分

思路与算法：

首先想到的是暴力法，用一个哈希表存储每个字母的出现次数，那么答案字符串的首字母至少出现 \(2\) 次，中间字符至少出现一次。

  1. 第一层循环 \(0 < i < len - 1\)，遍历整个字符串；
  2. 第二层循环，子字符串长度，\(i < j < len - i\)；
  3. 第三层循环，判断第二层循环的字符串在后续字符串中是否出现。

于是写出了下列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
36
public 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代码：

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
36
37
38
39
40
41
42
43
44
// Binary Search time: O(n^2logn) space: O(n)
// TimeOut
public static String longestDupSubstring_bs(String s) {
    int len = s.length();
    int[] cnt = new int[26];
    for (char ch : s.toCharArray()) {
        cnt[ch - 'a']++;
    }

    String ans = "";
    int maxLen = 0;

    for (int i = 0; i < len; i++) {
        if (cnt[s.charAt(i) - 'a'] < 2) {
            continue;
        }

        int ret = binarySearch(s, i, maxLen + 1, len - 1 - i);
        if (ret > maxLen) {
            maxLen = ret;
            ans = s.substring(i, i + maxLen);
        }
    }

    return ans;
}

public static int binarySearch(String s, int idx, int left, int right) {
    int ans = 0;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        String subStr = s.substring(idx, idx + mid);
        String rightSubStr = s.substring(idx + 1);
        if (rightSubStr.contains(subStr)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return ans;
}

复杂度分析

  • 时间复杂度：\(O(n^2 \log n)\)，其中 \(n\) 为字符串长度。
  • 空间复杂度：\(O(n)\)。哈希表和字符串均需要存储 \(n\) 个元素。

方法二：二分搜索 + 字符串Hash

思路与算法：

方法一代码会超时，我们需要寻求更加高效的解法。

通过看别人的题解，终于知道咋做了，方法是 Rabin-Karp 字符串编码 。浅显易懂的题解在 字符串哈希 。

代码如下所示：

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
36
37
38
39
40
41
42
43
public String longestDupSubstring(String s) {
    String ans = "";
    int len = s.length();
    int left = 0;
    int right = len - 1;
    while (left <= right) {
        int mid = left + (right - left + 1) / 2;
        String ret = searchWin(s, mid);
        if (ret.length() > 0) {
            left = mid + 1;
            ans = ret;
        } else {
            right = mid - 1;
        }
    }

    return ans;
}

public String searchWin(String s, int len) {
    int PRIME = 31;
    Set<Long> seen = new HashSet<>();
    long hash = 0;
    long power = 1;
    for (int i = 0; i < len; i++) {
        hash = PRIME * hash + s.charAt(i);
        power *= PRIME;
    }

    seen.add(hash);

    for (int i = len; i < s.length(); i++) {
        hash = PRIME * hash + s.charAt(i) - power * s.charAt(i - len);
        String subStr = s.substring(i - len + 1, i + 1);
        if (seen.contains(hash) && s.indexOf(subStr) != i) {
            return subStr;
        }

        seen.add(hash);
    }

    return "";
}

复杂度分析

  • 时间复杂度：\(O(n \log n)\) ，其中 \(n\) 为字符串长度。
  • 空间复杂度：\(O(n)\) 。

方法三：后缀数组

看题解发现还有后缀数组的解法，待学有余力时再来看看：

题解如下：

  1. 一题双解 :「字符串哈希 + 二分」&「后缀数组」

  2. O(n) 复杂度的后缀数组解法

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗