LeetCode 1044. 最长重复子串

2026-09-02 HGNULB 约 8 分钟

文章信息 11 个分类 10 个标签

分类

LeetCode CodeTop 困难未解决 20-50 字节跳动美团阿里巴巴快手腾讯亚马逊

题目描述

✅ 1044. 最长重复子串

题意分析

要在一个字符串里找出出现过至少两次的最长连续子串，并把子串本身返回出来（不是返回长度，也不是返回下标）。如果不存在这样的子串，返回空串。

关键的约束信号有两个。第一，两次出现允许重叠："aaaaa" 中 "aaaa" 出现在下标 0 和下标 1，虽然区间交叠，但仍然算重复，所以不能想当然地要求两段互不相交。第二，字符串长度可以到 $3 \times 10^4$ 量级，子串总数是 $O(n^2)$ 级别，逐个枚举并比较必然超时——这个规模摆明了要求一个带 $\log$ 的解法。

边界要注意：答案长度最多只能是 $n-1$，因为整串自己不可能在自己里出现第二次；n = 1 时直接无解；重复子串可能有多个，题目允许返回任意一个。

解法：二分长度 + 双滚动哈希

核心思路

设 check(L) 表示“存在长度为 L 的重复子串”。若 check(L) 成立，把两次出现各截短一位，check(L-1) 也一定成立，因此答案长度具有单调性，可以二分；每轮只需判断一个固定长度是否重复。

判定时枚举所有长度为 L 的窗口。滚动哈希用 $O(1)$ 时间从前一窗口更新到后一窗口，使一轮哈希扫描保持 $O(n)$。buckets[key] 的不变量是：其中保存了当前窗口之前、双哈希值同为 key 的全部起点。

哈希相同不等于字符串一定相同。代码先用两个大质数取模，显著减少碰撞；命中同一双哈希后，再逐字符比较对应区间。只有内容确实相同才返回，否则把当前起点也放入该桶继续扫描。因此碰撞最多影响运行时间，不会制造错误答案或漏掉真实重复串。

二分过程中，start/bestLen 始终保存已经验证过的最长可行解；成功就尝试更长，失败就缩短。窗口允许重叠，算法只比较内容和起点，不会错误地要求两个区间分离。

解题步骤

在 [1, n-1] 二分长度；长度 0 无需判断，整串也不可能出现两次。

对长度 L，计算首窗口的两组哈希及 $BASE^L$，把起点 0 放入对应桶。

窗口每右移一位，用 hash * BASE - leftChar * BASE^L + rightChar 更新两组哈希；减法后补模，保证结果非负。

当前双哈希命中桶时，与桶内每个历史窗口做精确区间比较；内容相同就返回当前起点，否则记录当前起点。

判定成功时记录起点和长度，并令左界右移；失败时令右界左移。

二分结束后按记录截取答案；从未成功则返回空串。

"banana" 中，check(3) 找到起点 1 和 3 的 "ana"，而 check(4) 失败，所以答案长度为 3。两段 "ana" 有重叠，仍是合法答案。

代码实现

import java.util.*;

class Solution {
    private static final long MOD1 = 1000000007L;
    private static final long MOD2 = 1000000009L;
    private static final long BASE = 131L;

    public String longestDupSubstring(String s) {
        int left = 1;
        int right = s.length() - 1;
        int start = -1;
        int bestLen = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int idx = findDuplicate(s, mid);
            if (idx >= 0) {
                start = idx;
                bestLen = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return start < 0 ? "" : s.substring(start, start + bestLen);
    }

    private int findDuplicate(String s, int len) {
        long hash1 = 0;
        long hash2 = 0;
        long power1 = 1;
        long power2 = 1;
        for (int i = 0; i < len; i++) {
            hash1 = (hash1 * BASE + s.charAt(i)) % MOD1;
            hash2 = (hash2 * BASE + s.charAt(i)) % MOD2;
            power1 = power1 * BASE % MOD1;
            power2 = power2 * BASE % MOD2;
        }

        Map<Long, List<Integer>> startsByHash = new HashMap<>();
        startsByHash.computeIfAbsent(combine(hash1, hash2), key -> new ArrayList<>()).add(0);

        for (int i = len; i < s.length(); i++) {
            hash1 = (hash1 * BASE - s.charAt(i - len) * power1 % MOD1 + MOD1 + s.charAt(i)) % MOD1;
            hash2 = (hash2 * BASE - s.charAt(i - len) * power2 % MOD2 + MOD2 + s.charAt(i)) % MOD2;
            long key = combine(hash1, hash2);
            int start = i - len + 1;

            List<Integer> candidates = startsByHash.get(key);
            if (candidates != null) {
                for (int previous : candidates) {
                    if (s.regionMatches(previous, s, start, len)) {
                        return start;
                    }
                }
            }
            startsByHash.computeIfAbsent(key, value -> new ArrayList<>()).add(start);
        }
        return -1;
    }

    private long combine(long first, long second) {
        return (first << 32) | second;
    }
}

func longestDupSubstring(s string) string {
    left := 1
    right := len(s) - 1
    start := -1
    bestLen := 0

    for left <= right {
        mid := left + (right-left)/2
        idx := findDuplicateSubstring(s, mid)
        if idx >= 0 {
            start = idx
            bestLen = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    if start < 0 {
        return ""
    }
    return s[start : start+bestLen]
}

func findDuplicateSubstring(s string, length int) int {
    const mod1 int64 = 1000000007
    const mod2 int64 = 1000000009
    const base int64 = 131
    hash1 := int64(0)
    hash2 := int64(0)
    power1 := int64(1)
    power2 := int64(1)

    for i := 0; i < length; i++ {
        hash1 = (hash1*base + int64(s[i])) % mod1
        hash2 = (hash2*base + int64(s[i])) % mod2
        power1 = power1 * base % mod1
        power2 = power2 * base % mod2
    }

    startsByHash := map[int64][]int{combineHash(hash1, hash2): []int{0}}
    for i := length; i < len(s); i++ {
        hash1 = (hash1*base - int64(s[i-length])*power1%mod1 + mod1 + int64(s[i])) % mod1
        hash2 = (hash2*base - int64(s[i-length])*power2%mod2 + mod2 + int64(s[i])) % mod2
        key := combineHash(hash1, hash2)
        start := i - length + 1

        for _, previous := range startsByHash[key] {
            if s[previous:previous+length] == s[start:start+length] {
                return start
            }
        }
        startsByHash[key] = append(startsByHash[key], start)
    }
    return -1
}

func combineHash(first int64, second int64) int64 {
    return first<<32 | second
}

复杂度分析

期望时间复杂度：$O(n\log n)$。二分进行 $O(\log n)$ 轮，每轮滚动扫描 $O(n)$；双哈希使误碰撞极少，真正重复通常在首次精确比较时返回。

最坏时间复杂度：若刻意构造大量双哈希碰撞，桶内逐一比较可能退化到 $O(n^3\log n)$。精确比较保证结果仍正确；若面试要求确定性的最坏界，应改用后缀数组配合 LCP。

空间复杂度：$O(n)$，一轮判定最多保存所有窗口起点。

关键点总结

先证明“存在长度为 L 的重复串”具有单调性，再二分答案长度。

滚动公式里的幂必须与公式配套：当前写法需要减去 leftChar * BASE^L。

双哈希降低碰撞概率，桶内精确比较消除碰撞对正确性的影响；两者职责不同。

判定函数要返回起点而不只是布尔值，二分成功时同步保存，才能还原最终子串。

重复串允许重叠；若要求确定性 $O(n\log n)$，可讨论后缀数组，而不是假装哈希绝对无碰撞。

易错点总结

漏存首窗口："aa" 在判断长度 1 时会漏掉起点 0 与 1 的匹配。

幂次数写错：公式 hash * BASE - left * power 对应 power = BASE^L，不是 $BASE^{L-1}$。

负数取模未归一化：Java、Go 的负数 % 仍可能为负，减法后要先加模数。

把哈希相等当内容相等：即使双哈希也存在理论碰撞；必须检查桶内窗口的真实内容。

每个哈希只存一个起点：若该起点只是碰撞串，后续真正重复的窗口可能被漏掉，因此碰撞桶要保留全部未匹配起点。

二分成功却不保存起点：最终只能得到长度，无法返回题目要求的子串。

禁止重叠："aaaaa" 的最长答案是起点 0、1 上重叠的 "aaaa"，不能加区间不相交条件。

相似题目

题目	难度	考察点
1062. 最长重复子串的长度	中等	同一模型但只要长度，数据更小，可用区间 DP 兜底
187. 重复的DNA序列	中等	长度固定为 10，无需二分，直接单轮滚动哈希去重
718. 最长重复子数组	中等	两个数组之间求公共段，主解是二维 DP 而非自重复
28. 找出字符串中第一个匹配项的下标	简单	模式串已给定，滚动哈希退化为定长匹配，可对比 KMP