05 August 2008
给一个字符串 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);
}
}