1044. 最长重复子串
题目描述
输入字符串 s。如果 s 的某个连续子串在 s 中至少出现两次，就称它为重复子串。两次出现的位置允许重叠。
返回长度最长的重复子串。有多个长度相同的答案时，返回其中任意一个。如果不存在重复子串，返回空串 ""。
示例 1
输入：s = "banana" 输出："ana"
解释：ana 在下标 1 和 3 处各出现一次，两处有重叠。
示例 2
输入：s = "abcd" 输出：""
解释：四个字母各不相同，没有重复子串。
数据范围
2 <= s.length <= 3 * 10^4s只含小写英文字母。
解题思路：二分长度 + 滚动哈希
如果长度 L 的子串有重复，那么更短的长度也一定有重复（取它的前缀即可），所以可以对长度 L 二分。判断“长度 L 是否有重复”时，用 Rabin-Karp 滚动哈希：窗口右移一格，哈希值去掉最左字符、加入新字符，O(1) 更新；哈希相同的再逐字比较，排除冲突。
为什么正确
二分过程中，长度 < lo 的都已确认有重复（ans 记录其中最长的一个），长度 > hi 的都已确认没有重复。
复杂度分析
时间 O(n log n)（期望），空间 O(n)。
易错点
哈希相等不代表子串相等，必须逐字确认或使用双哈希。减去最左字符后取模可能为负，C++/Java/Go/JS 要加 M 再取模。乘法 h*B 和 c*B^L 需要 64 位整数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def longestDupSubstring(self, s: str) -> str:
n, B, M = len(s), 131, 1000000007
def dup(L):
p = pow(B, L, M)
h, seen = 0, {}
for i in range(n):
h = (h * B + ord(s[i])) % M
if i >= L:
h = (h - ord(s[i - L]) * p) % M
if i >= L - 1:
st = i - L + 1
for j in seen.get(h, []):
if s[j:j + L] == s[st:st + L]:
return st
seen.setdefault(h, []).append(st)
return -1
lo, hi, ans = 1, n - 1, ""
while lo <= hi:
mid = (lo + hi) // 2
st = dup(mid)
if st >= 0:
ans, lo = s[st:st + mid], mid + 1
else:
hi = mid - 1
return ansclass Solution {
public String longestDupSubstring(String s) {
int n = s.length(); long B = 131, M = 1000000007L;
int lo = 1, hi = n - 1; String ans = "";
while (lo <= hi) {
int mid = (lo + hi) / 2;
int st = dup(s, mid, B, M);
if (st >= 0) {
ans = s.substring(st, st + mid); lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
private int dup(String s, int L, long B, long M) {
int n = s.length();
long p = 1; for (int k = 0; k < L; k++) p = p * B % M;
long h = 0; java.util.HashMap<Long, java.util.List<Integer>> seen = new java.util.HashMap<>();
for (int i = 0; i < n; i++) {
h = (h * B + s.charAt(i)) % M;
if (i >= L) {
h = ((h - s.charAt(i - L) * p) % M + M) % M;
}
if (i >= L - 1) {
int st = i - L + 1;
for (int j : seen.getOrDefault(h, java.util.Collections.emptyList())) {
if (s.regionMatches(j, s, st, L)) {
return st;
}
}
seen.computeIfAbsent(h, k -> new java.util.ArrayList<>()).add(st);
}
}
return -1;
}
}class Solution {
public:
string longestDupSubstring(string s) {
long long n = s.size(), B = 131, M = 1000000007;
auto dup = [&](int L) -> int {
long long p = 1; for (int k = 0; k < L; k++) p = p * B % M;
long long h = 0; unordered_map<long long, vector<int>> seen;
for (int i = 0; i < n; i++) {
h = (h * B + (unsigned char)s[i]) % M;
if (i >= L) {
h = ((h - (long long)(unsigned char)s[i - L] * p) % M + M) % M;
}
if (i >= L - 1) {
int st = i - L + 1;
for (int j : seen[h]) {
if (s.compare(j, L, s, st, L) == 0) {
return st;
}
}
seen[h].push_back(st);
}
}
return -1;
};
int lo = 1, hi = n - 1; string ans = "";
while (lo <= hi) {
int mid = (lo + hi) / 2;
int st = dup(mid);
if (st >= 0) {
ans = s.substr(st, mid); lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
};func longestDupSubstring(s string) string {
n, B, M := len(s), int64(131), int64(1000000007)
dup := func(L int) int {
p := int64(1); for k := 0; k < L; k++ { p = p * B % M }
h, seen := int64(0), map[int64][]int{}
for i := 0; i < n; i++ {
h = (h*B + int64(s[i])) % M
if i >= L {
h = ((h-int64(s[i-L])*p)%M + M) % M
}
if i >= L-1 {
st := i - L + 1
for _, j := range seen[h] {
if s[j:j+L] == s[st:st+L] {
return st
}
}
seen[h] = append(seen[h], st)
}
}
return -1
}
lo, hi, ans := 1, n-1, ""
for lo <= hi {
mid := (lo + hi) / 2
st := dup(mid)
if st >= 0 {
ans, lo = s[st:st+mid], mid+1
} else {
hi = mid - 1
}
}
return ans
}var longestDupSubstring = function(s) {
const n = s.length, B = 131, M = 1000000007;
const dup = (L) => {
let p = 1; for (let k = 0; k < L; k++) p = p * B % M;
let h = 0; const seen = new Map();
for (let i = 0; i < n; i++) {
h = (h * B + s.charCodeAt(i)) % M;
if (i >= L) {
h = ((h - s.charCodeAt(i - L) * p) % M + M) % M;
}
if (i >= L - 1) {
const st = i - L + 1;
for (const j of (seen.get(h) || [])) {
if (s.substr(j, L) === s.substr(st, L)) {
return st;
}
}
if (!seen.has(h)) seen.set(h, []); seen.get(h).push(st);
}
}
return -1;
};
let lo = 1, hi = n - 1, ans = "";
while (lo <= hi) {
const mid = (lo + hi) >> 1;
const st = dup(mid);
if (st >= 0) {
ans = s.substr(st, mid); lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
};function longestDupSubstring(s: string): string {
const n = s.length, B = 131, M = 1000000007;
const dup = (L: number): number => {
let p = 1; for (let k = 0; k < L; k++) p = p * B % M;
let h = 0; const seen = new Map<number, number[]>();
for (let i = 0; i < n; i++) {
h = (h * B + s.charCodeAt(i)) % M;
if (i >= L) {
h = ((h - s.charCodeAt(i - L) * p) % M + M) % M;
}
if (i >= L - 1) {
const st = i - L + 1;
for (const j of (seen.get(h) || [])) {
if (s.substr(j, L) === s.substr(st, L)) {
return st;
}
}
if (!seen.has(h)) seen.set(h, []); seen.get(h).push(st);
}
}
return -1;
};
let lo = 1, hi = n - 1, ans = "";
while (lo <= hi) {
const mid = (lo + hi) >> 1;
const st = dup(mid);
if (st >= 0) {
ans = s.substr(st, mid); lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}其他解法
二分哈希利用“长度 L 有重复则更短也有重复”的单调性，代码较短但依赖哈希（本题主解法碰到哈希相同时会逐字符核对）；后缀数组一次构造后直接读出最大 LCP，是确定性算法，还能解决不同子串计数等更多问题。
解法 2：后缀数组 + LCP 时间 O(n log² n)，空间 O(n)
任何重复子串都是两个不同后缀的公共前缀。把所有后缀按字典序排序得到后缀数组，那么最长公共前缀一定出现在字典序相邻的两个后缀之间。后缀数组用倍增法构造：第 k 轮用前一轮长度 k 的排名对 (rank[i], rank[i+k]) 排序，得到长度 2k 的排名，直到所有排名互不相同。再用 Kasai 算法按原串顺序求每个后缀与其字典序前一个后缀的公共前缀长度，利用“下一个位置的 LCP 至少为当前减 1”的性质在 O(n) 内算完。最大的 LCP 对应的前缀就是答案。
结果确定，没有哈希冲突的风险，而且后缀数组是处理字符串重复类问题的通用工具。实现比二分哈希复杂，倍增法用比较排序时多一个 log 因子，换成基数排序可以降到 O(n log n)。
class Solution:
def longestDupSubstring(self, s: str) -> str:
n = len(s)
base = max(n, 256) + 2
rank = [ord(c) for c in s]
sa = list(range(n))
k = 1
while True:
key = [rank[i] * base + (rank[i + k] + 1 if i + k < n else 0) for i in range(n)]
sa.sort(key=key.__getitem__)
nr = [0] * n
for j in range(1, n):
nr[sa[j]] = nr[sa[j - 1]] + (key[sa[j]] != key[sa[j - 1]])
rank = nr
if rank[sa[-1]] == n - 1:
break
k <<= 1
best = pos = h = 0
for i in range(n):
if rank[i] == 0:
h = 0
continue
j = sa[rank[i] - 1]
while i + h < n and j + h < n and s[i + h] == s[j + h]:
h += 1
if h > best:
best, pos = h, i
if h:
h -= 1
return s[pos:pos + best]class Solution {
public String longestDupSubstring(String s) {
int n = s.length();
long base = Math.max(n, 256) + 2;
int[] rank = new int[n];
Integer[] sa = new Integer[n];
long[] key = new long[n];
for (int i = 0; i < n; i++) {
rank[i] = s.charAt(i);
sa[i] = i;
}
for (int k = 1;; k <<= 1) {
for (int i = 0; i < n; i++) key[i] = rank[i] * base + (i + k < n ? rank[i + k] + 1 : 0);
Arrays.sort(sa, (a, b) -> Long.compare(key[a], key[b]));
int[] nr = new int[n];
for (int j = 1; j < n; j++) nr[sa[j]] = nr[sa[j - 1]] + (key[sa[j]] != key[sa[j - 1]] ? 1 : 0);
rank = nr;
if (rank[sa[n - 1]] == n - 1) break;
}
int best = 0, pos = 0, h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] == 0) {
h = 0;
continue;
}
int j = sa[rank[i] - 1];
while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) h++;
if (h > best) {
best = h;
pos = i;
}
if (h > 0) h--;
}
return s.substring(pos, pos + best);
}
}class Solution {
public:
string longestDupSubstring(string s) {
int n = s.size();
long long base = max(n, 256) + 2;
vector<int> rank(n), sa(n), nr(n);
vector<long long> key(n);
for (int i = 0; i < n; i++) {
rank[i] = (unsigned char) s[i];
sa[i] = i;
}
for (int k = 1;; k <<= 1) {
for (int i = 0; i < n; i++) key[i] = rank[i] * base + (i + k < n ? rank[i + k] + 1 : 0);
sort(sa.begin(), sa.end(), [&](int a, int b) { return key[a] < key[b]; });
nr[sa[0]] = 0;
for (int j = 1; j < n; j++) nr[sa[j]] = nr[sa[j - 1]] + (key[sa[j]] != key[sa[j - 1]]);
rank = nr;
if (rank[sa[n - 1]] == n - 1) break;
}
int best = 0, pos = 0, h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] == 0) {
h = 0;
continue;
}
int j = sa[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
if (h > best) {
best = h;
pos = i;
}
if (h) h--;
}
return s.substr(pos, best);
}
};func longestDupSubstring(s string) string {
n := len(s)
base := max(n, 256) + 2
rank := make([]int, n)
sa := make([]int, n)
key := make([]int, n)
for i := 0; i < n; i++ {
rank[i] = int(s[i])
sa[i] = i
}
for k := 1; ; k <<= 1 {
for i := 0; i < n; i++ {
key[i] = rank[i] * base
if i+k < n {
key[i] += rank[i+k] + 1
}
}
sort.Slice(sa, func(a, b int) bool { return key[sa[a]] < key[sa[b]] })
nr := make([]int, n)
for j := 1; j < n; j++ {
nr[sa[j]] = nr[sa[j-1]]
if key[sa[j]] != key[sa[j-1]] {
nr[sa[j]]++
}
}
rank = nr
if rank[sa[n-1]] == n-1 {
break
}
}
best, pos, h := 0, 0, 0
for i := 0; i < n; i++ {
if rank[i] == 0 {
h = 0
continue
}
j := sa[rank[i]-1]
for i+h < n && j+h < n && s[i+h] == s[j+h] {
h++
}
if h > best {
best, pos = h, i
}
if h > 0 {
h--
}
}
return s[pos : pos+best]
}var longestDupSubstring = function(s) {
const n = s.length;
const base = Math.max(n, 256) + 2;
let rank = new Array(n);
const sa = new Array(n);
const key = new Array(n);
for (let i = 0; i < n; i++) {
rank[i] = s.charCodeAt(i);
sa[i] = i;
}
for (let k = 1; ; k <<= 1) {
for (let i = 0; i < n; i++) key[i] = rank[i] * base + (i + k < n ? rank[i + k] + 1 : 0);
sa.sort((a, b) => key[a] - key[b]);
const nr = new Array(n).fill(0);
for (let j = 1; j < n; j++) nr[sa[j]] = nr[sa[j - 1]] + (key[sa[j]] !== key[sa[j - 1]] ? 1 : 0);
rank = nr;
if (rank[sa[n - 1]] === n - 1) break;
}
let best = 0, pos = 0, h = 0;
for (let i = 0; i < n; i++) {
if (rank[i] === 0) {
h = 0;
continue;
}
const j = sa[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
if (h > best) {
best = h;
pos = i;
}
if (h > 0) h--;
}
return s.substring(pos, pos + best);
};function longestDupSubstring(s: string): string {
const n = s.length;
const base = Math.max(n, 256) + 2;
let rank: number[] = new Array(n);
const sa: number[] = new Array(n);
const key: number[] = new Array(n);
for (let i = 0; i < n; i++) {
rank[i] = s.charCodeAt(i);
sa[i] = i;
}
for (let k = 1; ; k <<= 1) {
for (let i = 0; i < n; i++) key[i] = rank[i] * base + (i + k < n ? rank[i + k] + 1 : 0);
sa.sort((a, b) => key[a] - key[b]);
const nr: number[] = new Array(n).fill(0);
for (let j = 1; j < n; j++) nr[sa[j]] = nr[sa[j - 1]] + (key[sa[j]] !== key[sa[j - 1]] ? 1 : 0);
rank = nr;
if (rank[sa[n - 1]] === n - 1) break;
}
let best = 0, pos = 0, h = 0;
for (let i = 0; i < n; i++) {
if (rank[i] === 0) {
h = 0;
continue;
}
const j = sa[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
if (h > best) {
best = h;
pos = i;
}
if (h > 0) h--;
}
return s.substring(pos, pos + best);
}