GuilinDev

Lc1044

05 August 2008

1044. Longest Duplicate Substring

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

返回 任意一个 具有最长长度的重复子串。如果 s 不含重复子串,那么答案为 “” 。

字符串哈希 + 二分

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

小于等于最大长度方案均存在(考虑在最大长度方案上做删减); 大于最大长度的方案不存在。 二分范围为 [0, n],关键在于如何 check 函数,即实现「检查某个长度 len 作为最大长度,是否存在合法方案」。

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

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

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

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

O(nlogn)

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
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 result = "";
        int left = 0, right = n;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            String t = check(s, mid);
            if (t.length() != 0) left = mid;
            else right = mid - 1;
            result = t.length() > result.length() ? t : result;
        }
        return result;
    }

    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 "";
    }
}

后缀数组

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

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

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

sa 数组:字典序排名为 ii 的后缀是第几个;

rk 数组:第 ii 个后缀的排名是多少(不难发现 rk 与 sa 满足 sa[rk[i]] = rk[sa[i]] = isa[rk[i]]=rk[sa[i]]=i);

height 数组:存储 sa[i]sa[i] 与 sa[i - 1]sa[i−1] 的 LCP(最长公共前缀) 为何值。

O(nlogn)

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
63
64
65
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();
        System.arraycopy(b, 0, a, 0, n);
        System.arraycopy(c, 0, b, 0, n);
    }

    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);
    }
}