LeetCode 1044. 最长重复子串

2026-09-02 HGNULB 约 8 分钟

文章信息 12 个分类 6 个标签

分类

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

题目描述

✅ 1044. 最长重复子串

题意分析

在字符串 s 中找一个出现至少两次、长度尽可能长的连续子串。两次出现必须来自不同起点，但允许它们覆盖的区间重叠；有多个最长答案时，返回任意一个即可。

这里要求连续子串，不是可以跳过字符的子序列。如果没有任何重复子串，返回空字符串。字符串只包含小写英文字母，下面按字符位置枚举各个定长窗口。

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

核心思路

[!blue]

先把“求最长”转成“是否存在长度为 L 的重复子串”。如果两个长度为 L 的窗口相同，它们任意更短的同长度前缀也相同；反过来，长度 L 都不存在重复，更长的重复也不可能存在。可行长度因此是连续前缀，可以二分查找最大的可行值。

对一个固定长度 L，从左到右检查所有窗口。直接反复比较整段字符串成本较高，可以先计算窗口的哈希值，把可能相同的窗口放在同一桶中。代码使用两个不同模数的滚动哈希，并把它们组合成一个键，降低不同字符串落入同一桶的机会。

一个窗口的哈希按从左到右“乘 BASE 再加当前字符”计算。窗口右移时，先把旧哈希乘以 BASE，原来最左字符的贡献就变成了 leftChar * BASE^L；减去它，再加入新字符，就得到新窗口哈希。因此当前公式是 hash * BASE - leftChar * BASE^L + rightChar，两组哈希分别对各自模数取模。

哈希相等不能直接认定内容相同。每个桶保留所有历史起点，命中时逐一与当前窗口精确比较，真正相同才返回当前起点。若只是发生碰撞，就把当前起点也存进去，供后面的窗口比较；只留一个代表可能让其他真实重复窗口被碰撞串挡住。

二分判定成功后，同时保存当前起点和长度，并继续尝试更长区间；失败就尝试更短区间。精确比较保证判定结果正确，哈希碰撞只会增加比较工作，不会制造错误答案。所有窗口按起点枚举，整个过程无需排除重叠。

解题步骤

将二分范围设为 [1, n - 1]，用未找到的起点和长度零初始化答案。

判定长度 L 时，计算首窗口的两组哈希及各自的 BASE^L，记录首窗口起点 0。

逐次右移窗口，按滚动公式去掉旧字符、加入新字符，并把取模结果规范到非负范围。

双哈希命中历史桶时，精确比较桶内所有候选区间；找到相同内容则返回起点，否则保存当前起点。

若存在重复，记录结果并令二分左界越过当前长度；否则降低右界。

二分结束后按保存的起点、长度截取子串；从未成功则返回空串。

代码实现

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
}

复杂度分析

设字符串长度为 $n$。

时间复杂度：哈希碰撞较少时通常为 $O(n\log n)$。每次判定线性滚动扫描，二分需要 $O(\log n)$ 次判定；成功时的一次精确比较最多也只扫描 $n$ 个字符。

最坏时间复杂度：固定双哈希不提供无碰撞保证。保守地按每轮 $O(n^2)$ 对候选、每次比较 $O(n)$ 计算，上界为 $O(n^3\log n)$；精确比较保证结果正确，但不能保证最坏耗时仍是线性判定。

辅助空间复杂度：$O(n)$，每轮最多保存所有窗口的起点，窗口内容直接从原串读取。

关键点总结

[!green]

重复子串的存在性对长度具有单调性，因此能够二分答案。

哈希筛选候选，精确区间比较确认相等，不能省略后者。

同哈希桶保存全部历史起点，避免碰撞导致漏掉真实重复。

判定成功时保存起点与长度，最终才能还原答案。

易错点总结

[!yellow]

首窗口也要先入桶，否则后面的窗口无法与起点 0 比较。

当前滚动公式先乘底数，再移出左字符，移出项必须使用 BASE^L，不能写成 BASE^(L - 1)。

减法取模后要保证哈希值非负，避免相同窗口因表示不同而落入不同键。

即使双哈希相同，也必须核对原串；仅保留桶内一个起点也可能被碰撞干扰。

二分成功后不能只记录长度，还要保存这次找到的起点。

题目允许重复区间重叠，不能额外限制两次出现互不相交。

相似题目

题目	难度	关联与区别
187. 重复的DNA序列	中等	原题重复片段长度固定，可直接滚动编码，本题需要寻找最大可行长度。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/15857477

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！