题目描述
这是 LeetCode 上的 1044. 最长重复子串 ，难度为 困难。
Tag : 「字符串哈希」、「二分」、「后缀数组」
给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的连续子串，在 s 中出现 22 次或更多次。这些出现之间可能存在重叠。
返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。
示例 1：
输入：s = "banana" 输出："ana" 复制代码
示例 2：
输入：s = "abcd" 输出："" 复制代码
提示：
- 2 <= s.length <= 3 * 10^42<=s.length<=3∗104
s由小写英文字母组成
字符串哈希 + 二分
题目要求得「能取得最大长度的任一方案」，首先以「最大长度」为分割点的数轴具有「二段性」：
- 小于等于最大长度方案均存在（考虑在最大长度方案上做删减）；
- 大于最大长度的方案不存在。
二分范围为 [0, n][0,n]，关键在于如何 check 函数，即实现「检查某个长度 lenlen 作为最大长度，是否存在合法方案」。
对于常规做法而言，可枚举每个位置作为起点，得到长度为 lenlen 的子串，同时使用 Set<String> 容器记录已被处理过子串有哪些，当容器中出现过当前子串，说明存在合法方案。
但是该做法实现的 check 并非线性，子串的生成和存入容器的时执行的哈希函数执行均和子串长度相关，复杂度是 O(n * len)O(n∗len)。
我们可以通过「字符串哈希」进行优化，对「字符串哈希」不熟悉的同学可以看前置 🧀 字符串哈希入门。
具体的，在二分前先通过 O(n)O(n) 的复杂度预处理出哈希数组，从而确保能够在 check 时能够 O(1)O(1) 得到某个子串的哈希值，最终将 check 的复杂度降为 O(n)O(n)。
代码：
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 ""; } } 复制代码
- 时间复杂度：令 nn 为字符串
s的长度，预处理出哈希数组的复杂度为 O(n)O(n)；二分最大长度的复杂度为 O(n\log{n})O(nlogn)；整体复杂度为 O(n\log{n})O(nlogn) - 空间复杂度：O(n)O(n)
后缀数组
另外一个较为进阶的做法是使用「后缀数组」，后缀数组有基于基数排序的倍增实现，复杂度为 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（最长公共前缀）为何值。
代码：
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(nlogn)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1044 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
