LC 1044. 最长重复子串

题目描述

这是 LeetCode 上的 1044. 最长重复子串 ，难度为 困难。

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

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

示例 1：

1
2
3
输入：s = "banana"

输出："ana"

示例 2：
1
2
3
输入：s = "abcd"

输出：""

提示：

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

字符串哈希 + 二分

题目要求得「能取得最大长度的任一方案」，首先以「最大长度」为分割点的数轴具有「二段性」：

  • 小于等于最大长度方案均存在（考虑在最大长度方案上做删减）；
  • 大于最大长度的方案不存在。

二分范围为 $[0, n]$，关键在于如何 check 函数，即实现「检查某个长度 $len$ 作为最大长度，是否存在合法方案」。

对于常规做法而言，可枚举每个位置作为起点，得到长度为 $len$ 的子串，同时使用 Set<String> 容器记录已被处理过子串有哪些，当容器中出现过当前子串，说明存在合法方案。

但是该做法实现的 check 并非线性，子串的生成和存入容器的时执行的哈希函数执行均和子串长度相关，复杂度是 $O(n * len)$。

我们可以通过「字符串哈希」进行优化，对「字符串哈希」不熟悉的同学可以看前置 🧀 字符串哈希入门。

具体的，在二分前先通过 $O(n)$ 的复杂度预处理出哈希数组，从而确保能够在 check 时能够 $O(1)$ 得到某个子串的哈希值，最终将 check 的复杂度降为 $O(n)$。

代码：

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
class Solution {
    long[] h, p;
    public String longestDupSubstring(String s) {
        int P = 1313131, n = s.length();
        h = new long[n + 10]; p = new long[n + 10];
        p[0] = 1;
        for (int i = 0; i < n; i++) {
            p[i + 1] = p[i] * P;
            h[i + 1] = h[i] * P + s.charAt(i);
        }
        String ans = "";
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            String t = check(s, mid);
            if (t.length() != 0) l = mid;
            else r = mid - 1;
            ans = t.length() > ans.length() ? t : ans;
        }
        return ans;
    }
    String check(String s, int len) {
        int n = s.length();
        Set<Long> set = new HashSet<>();
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            long cur = h[j] - h[i - 1] * p[j - i + 1];
            if (set.contains(cur)) return s.substring(i - 1, j);
            set.add(cur);
        }
        return "";
    }
}

  • 时间复杂度：令 $n$ 为字符串 s 的长度，预处理出哈希数组的复杂度为 $O(n)$；二分最大长度的复杂度为 $O(n\log{n})$；整体复杂度为 $O(n\log{n})$
  • 空间复杂度：$O(n)$

后缀数组

另外一个较为进阶的做法是使用「后缀数组」，后缀数组有基于基数排序的倍增实现，复杂度为 $O(n\log{n})$，也有基于 DC3 的 $O(n)$ 做法。

DC3 的做法已经写不出来了，写一个基于「基数排序」的倍增做法。

后缀数组包含几个核心数组：

  • sa 数组：字典序排名为 $i$ 的后缀是第几个；
  • rk 数组：第 $i$ 个后缀的排名是多少（不难发现 rk 与 sa 满足 $sa[rk[i]] = rk[sa[i]] = i$）；
  • height 数组：存储 $sa[i]$ 与 $sa[i - 1]$ 的 LCP（最长公共前缀） 为何值。

代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    int N = 30010;
    int[] x = new int[N], y = new int[N], c = new int[N];
    int[] sa = new int[N], rk = new int[N], height = new int[N];
    void swap(int[] a, int[] b) {
        int n = a.length;
        int[] c = a.clone();
        for (int i = 0; i < n; i++) a[i] = b[i];
        for (int i = 0; i < n; i++) b[i] = c[i];
    }
    public String longestDupSubstring(String s) {
        int n = s.length(), m = 128;
        s = " " + s;
        char[] cs = s.toCharArray();
        // sa：两遍基数排序，板子背不下来也可以直接使用 sort，复杂度退化到 n \log^2 n
        for (int i = 1; i <= n; i++) {
            x[i] = cs[i]; c[x[i]]++;
        }
        for (int i = 2; i <= m; i++) c[i] += c[i - 1];
        for (int i = n; i > 0; i--) sa[c[x[i]]--] = i;
        for (int k = 1; k <= n; k <<= 1) {
            int cur = 0;
            for (int i = n - k + 1; i <= n; i++) y[++cur] = i;
            for (int i = 1; i <= n; i ++) {
                if (sa[i] > k) y[++cur] = sa[i] - k;
            }
            for (int i = 1; i <= m; i++) c[i] = 0;
            for (int i = 1; i <= n; i++) c[x[i]]++;
            for (int i = 2; i <= m; i++) c[i] += c[i - 1];
            for (int i = n; i > 0; i--) {
                sa[c[x[y[i]]]--] = y[i];
                y[i] = 0;
            }
            swap(x, y);
            x[sa[1]] = cur = 1;
            for (int i = 2; i <= n; i++) {
                if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = cur;
                else x[sa[i]] = ++cur;
            }
            if (cur == n) break;
            m = cur;
        }
        // height
        int k = 0;
        for (int i = 1; i <= n; i ++) rk[sa[i]] = i;
        for (int i = 1; i <= n; i++) {
            if (rk[i] == 1) continue;
            int j = sa[rk[i] - 1];
            k = k > 0 ? k - 1 : k;
            while (i + k <= n && j + k <= n && cs[i + k] == cs[j + k]) k++;
            height[rk[i]] = k;
        }
        int idx = -1, max = 0;
        for (int i = 1; i <= n; i++) {
            if (height[i] > max) {
                max = height[i];
                idx = sa[i];
            }
        }
        return max == 0 ? "" : s.substring(idx, idx + max);
    }
}

  • 时间复杂度：$O(n\log{n})$
  • 空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1044 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。