LeetCode 1062. 最长重复子串的长度

2026-08-06 HGNULB 约 12 分钟

文章信息 8 个分类 8 个标签

分类

题目描述

✅ 1062. 最长重复子串的长度

题意分析

给定一个字符串 s，要找出其中最长的、在 s 里至少出现过两次的子串，返回它的长度。这里的两次出现允许重叠，只要起始位置不同就算两次，比如 "aaa" 里长度为 2 的 "aa" 分别从下标 0 和 1 开始，就算重复出现。如果不存在任何重复子串，返回 0。

题目问的是长度而不是子串本身，这一点很重要——它意味着我们只需要一个能回答「是否存在」的判定器，不必真的把子串取出来比较。

约束里的信号有两条。第一，字符串长度不超过 2000，$O(n^2)$ 量级可行但 $O(n^3)$ 会超时，这个规模恰好卡在「朴素枚举加逐字符比较不行、但枚举加常数时间判定可以」的位置。第二，字符集只有小写字母，取值范围小且连续，非常适合映射成小整数参与数值化计算。

边界方面：长度为 1 的串必然返回 0；全部字符互不相同的串也返回 0；答案的上界不是 n 而是 n - 1，因为长度为 n 的子串只有一个，不可能出现两次，不过把上界写成 n 也无妨，判定器自然会否掉它。

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

核心思路

最朴素的做法是枚举所有子串的起点和长度，再用哈希表记录见过的子串。子串数量是 $O(n^2)$ 级别，而每个子串的截取和比较又要 $O(n)$，总代价 $O(n^3)$，在 n 为 2000 时是八十亿次字符操作，完全不可行。瓶颈有两处：一是候选长度被逐个试遍，二是每个子串的相等判断花了线性时间。

先解决第一处。观察这样一个性质：如果存在长度为 L 的重复子串，那么它的任意一个长度为 L - 1 的前缀也在两个不同位置出现过，所以长度 L - 1 的重复子串也必然存在。反过来说，如果长度 L 不可行，那么任何大于 L 的长度都不可行。于是「是否存在长度为 L 的重复子串」这个谓词关于 L 单调，可以对 L 做二分，把 n 次尝试压成 $\log n$ 次。

再解决第二处。要在常数时间内比较任意两个等长子串，就得给每个子串算一个能 $O(1)$ 取到的数值指纹。把字符串看成一个 BASE 进制的大数，预处理前缀值 pre[i] = s[0..i) 对应的数，那么子串 s[i, i + L) 的值就是 pre[i + L] - pre[i] * BASE^L，全部在模意义下运算即可 $O(1)$ 求出。同一长度下把所有指纹丢进哈希集合，一旦插入失败就说明找到了重复。

于是不变量可以写成：二分维护的区间 [left, right] 始终包含真正的答案，其中 left 是已知可行的最大长度、right 是尚未被排除的最大候选；而判定函数 exists(L) 的语义是「s 中存在两个起点不同、长度为 L 的相同子串」，它靠一次线性扫描和 $O(1)$ 的子串指纹计算完成。

单模数哈希在 2000 个子串的规模下碰撞概率虽低但并非可以忽略，尤其面对刻意构造的数据，因此代码同时用了两组互不相同的大质数模数，把两个指纹拼成一个 64 位的键，碰撞概率降到可以放心的程度。

解题步骤

第一步，预处理四个长度为 n + 1 的数组：pow1、pow2 存 BASE 的各次幂，pre1、pre2 存两套模数下的前缀哈希。选择长度 n + 1 而不是 n，是为了让下标 0 表示空前缀，这样任意子串区间 [i, i + L) 都能用 pre[i + L] 与 pre[i] 相减表达，不必对起点为 0 的情况另开分支。

第二步，把字符映射成 s.charAt(i) - 'a' + 1。加一是必要的：如果 'a' 被映射成 0，那么 "a"、"aa"、"aaa" 的哈希值都会是 0，前导字符被静默吞掉，不同长度的串会撞在一起。

第三步，按 pre[i + 1] = (pre[i] * BASE + v) % MOD 递推前缀哈希，同时按 pow[i + 1] = pow[i] * BASE % MOD 递推幂次。两者必须用同一个 BASE 和同一个 MOD，否则后面的减法公式不成立。

第四步，令 left = 0、right = n 开始二分。左端取 0 是因为「长度为 0 的重复子串」平凡成立，这样可以保证区间里至少有一个可行值，最终返回的 left 天然覆盖了「无重复子串」时应返回 0 的情况。

第五步，取中点 mid = (left + right + 1) / 2。这里必须向上取整，因为下面的更新方式是「可行时 left = mid、不可行时 right = mid - 1」；如果向下取整，当区间只剩两个数且 mid 等于 left 并且可行时，left = mid 不会让区间缩小，循环就永远停不下来。

第六步，调用 exists(mid)。可行则说明答案至少是 mid，把下界抬到 mid（保留 mid 本身，因为它可能就是答案）；不可行则说明 mid 及以上全部无望，把上界压到 mid - 1。

第七步，在 exists 内部，对每个满足 i + len <= n 的起点 i 计算两套指纹。公式是 (pre[i + len] - pre[i] * pow[len] % MOD + MOD) % MOD：先取模再减，最后补一个 MOD 是为了消除减法可能产生的负数，Java 和 Go 的 % 对负数都返回负余数，不补就会得到负的哈希值并破坏比较。

第八步，把两个指纹合成一个键 (h1 << 32) ^ h2 存入集合。左移 32 位是因为单个哈希值小于 $10^9$ 即不超过 30 位，左移后与低位的 h2 不会互相干扰，等价于把两个哈希拼成一个 64 位整数一起比较。seen.add 返回 false 就意味着这个键之前出现过，立即返回 true。

第九步，循环结束后返回 left。此时 left 与 right 重合，指向最大的可行长度。

以 s = "banana" 走一遍：n 为 6，预处理出六个字符 b, a, n, a, n, a 的前缀哈希。二分区间初始为 [0, 6]。第一轮 mid = (0 + 6 + 1) / 2 = 3，调用 exists(3)，枚举起点 0 到 3 得到子串 ban、ana、nan、ana，第四个 ana 的指纹与第二个相同，插入失败，返回 true，于是 left = 3。第二轮区间 [3, 6]，mid = 5，exists(5) 枚举出 banan 和 anana，两者指纹不同，返回 false，于是 right = 4。第三轮区间 [3, 4]，mid = 4，exists(4) 枚举出 bana、anan、nana，互不相同，返回 false，right = 3。此时 left == right == 3，循环退出，返回 3，对应重复出现的 "ana"（起点 1 和起点 3），与预期一致。再看 s = "abcd"：mid = 2 时四个字符两两组合出 ab、bc、cd 互不相同返回 false，right = 1；mid = 1 时四个单字符也互不相同返回 false，right = 0；left == right == 0，返回 0。

代码实现

class Solution {
    // 使用滚动哈希快速计算所有长度为 L 的子串哈希。
    private static final long MOD1 = 1_000_000_007L;
    private static final long MOD2 = 1_000_000_009L;
    private static final long BASE = 131L;

    public int longestRepeatingSubstring(String s) {
        int n = s.length();
        long[] pow1 = new long[n + 1];
        long[] pow2 = new long[n + 1];
        long[] pre1 = new long[n + 1];
        long[] pre2 = new long[n + 1];
        pow1[0] = 1;
        pow2[0] = 1;
        for (int i = 0; i < n; i++) {
            int v = s.charAt(i) - 'a' + 1;
            pow1[i + 1] = pow1[i] * BASE % MOD1;
            pow2[i + 1] = pow2[i] * BASE % MOD2;
            pre1[i + 1] = (pre1[i] * BASE + v) % MOD1;
            pre2[i + 1] = (pre2[i] * BASE + v) % MOD2;
        }

        int left = 0;
        int right = n;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (exists(s, mid, pre1, pre2, pow1, pow2)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean exists(String s, int len, long[] pre1, long[] pre2, long[] pow1, long[] pow2) {
        if (len == 0) {
            return true;
        }
        int n = s.length();
        Set<Long> seen = new HashSet<>();
        for (int i = 0; i + len <= n; i++) {
            long h1 = (pre1[i + len] - pre1[i] * pow1[len] % MOD1 + MOD1) % MOD1;
            long h2 = (pre2[i + len] - pre2[i] * pow2[len] % MOD2 + MOD2) % MOD2;
            long key = (h1 << 32) ^ h2;
            if (!seen.add(key)) {
                return true;
            }
        }
        return false;
    }
}

func longestRepeatingSubstring(s string) int {
    // 使用滚动哈希快速计算所有长度为 L 的子串哈希。
    n := len(s)
    const mod1 int64 = 1_000_000_007
    const mod2 int64 = 1_000_000_009
    const base int64 = 131

    pow1 := make([]int64, n+1)
    pow2 := make([]int64, n+1)
    pre1 := make([]int64, n+1)
    pre2 := make([]int64, n+1)
    pow1[0], pow2[0] = 1, 1
    for i := 0; i < n; i++ {
        v := int64(s[i]-'a') + 1
        pow1[i+1] = pow1[i] * base % mod1
        pow2[i+1] = pow2[i] * base % mod2
        pre1[i+1] = (pre1[i]*base + v) % mod1
        pre2[i+1] = (pre2[i]*base + v) % mod2
    }

    left, right := 0, n
    for left < right {
        mid := (left + right + 1) / 2
        if existsRepeat(mid, n, pre1, pre2, pow1, pow2, mod1, mod2) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

func existsRepeat(length int, n int, pre1 []int64, pre2 []int64, pow1 []int64, pow2 []int64, mod1 int64, mod2 int64) bool {
    if length == 0 {
        return true
    }
    seen := make(map[uint64]struct{})
    for i := 0; i+length <= n; i++ {
        h1 := (pre1[i+length] - pre1[i]*pow1[length]%mod1 + mod1) % mod1
        h2 := (pre2[i+length] - pre2[i]*pow2[length]%mod2 + mod2) % mod2
        key := (uint64(h1) << 32) ^ uint64(h2)
        if _, ok := seen[key]; ok {
            return true
        }
        seen[key] = struct{}{}
    }
    return false
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 n 为字符串长度。预处理前缀哈希与幂次是一次线性扫描；二分把候选长度压到 $\log n$ 轮，每轮的判定函数枚举不超过 n 个起点、每个起点只做常数次乘法取模和一次哈希表操作。

空间复杂度：$O(n)$。四个长度为 n + 1 的长整型数组是固定开销，判定函数里的哈希集合最多同时存放 n 个键，两者都与字符串长度同阶。

关键点总结

先证明谓词的单调性再谈二分：本题的关键一步是「长度 L 可行则 L - 1 必可行」，只有单调才能二分答案，面试时必须显式说出这个论证而不是直接开二分。

把「求最优值」转成「判定可行性」：答案本身难算时，先设计一个便宜的 exists(x)，再让二分去逼近边界，这个套路适用于一大类最大化或最小化题目。

前缀哈希是等长子串比较的标准加速器：预处理出前缀值与幂次后，任意子串的指纹都能 $O(1)$ 取到，把 $O(n)$ 的字符串比较压成常数时间。

双模数是对抗构造数据的必要保险：单模数哈希在 2000 个子串的规模下仍有被针对的风险，用两组模数拼成 64 位键几乎可以杜绝碰撞，写的时候记得两套幂次数组要各自对应各自的模数。

上取整中点与左闭更新必须成对出现：只要更新方式是 left = mid，中点就必须写成 (left + right + 1) / 2，这条配套规则比死记二分模板更可靠。

面试视角：先给 $O(n^3)$ 暴力并点明两处瓶颈，再分别用二分和前缀哈希各消掉一处，最后主动说明哈希碰撞的风险与双模数的应对；如果面试官继续追问确定性算法，可以补充后缀数组配合最长公共前缀数组，或者用 dp[i][j] 表示以 i、j 结尾的最长公共后缀的 $O(n^2)$ 动态规划写法，并说明后者在 n 为 2000 时同样能过。

易错点总结

中点写成 (left + right) / 2 却仍用 left = mid 更新：s = "aa" 时区间收缩到 [1, 2] 后 mid 恒为 1 且可行，left 反复被赋成 1，循环永不退出。

字符映射成 s.charAt(i) - 'a' 而不加一：s = "aab" 中 "a" 和 "aa" 的哈希都是 0，长度判定被污染，exists(2) 会因为不同长度的串撞值而给出错误结论。

减法后不补 MOD：s = "banana" 计算中 pre[i + len] - pre[i] * pow[len] % MOD 极易为负，负的哈希值与正的哈希值永不相等，本该命中的重复被漏掉，答案偏小。

忘记先对 pre[i] * pow[len] 取模再相减：两个接近 $10^9$ 的数相乘约为 $10^{18}$，虽然仍在长整型范围内，但若把两次乘法或多个中间量叠加起来就会溢出，结果完全不可控。

只用一套模数：s 为 2000 个字符的构造串时，单模数在生日悖论下有实打实的碰撞概率，exists 会误报存在重复，最终答案偏大。

拼键时左移位数不足，例如写成 (h1 << 20) ^ h2：两个哈希的比特区间重叠，不同的 (h1, h2) 组合可能拼出同一个键，双模数的保护形同虚设。

判定函数忘记处理 len == 0：二分的下界就是 0，s = "abc" 时若对长度 0 走进循环，空子串的指纹恒为 0 且起点有 n + 1 个，会立刻误报 true，虽然结论碰巧不影响最终答案，但逻辑上是靠运气。

枚举起点时把条件写成 i + len < n：s = "aa"、len = 1 时只枚举到起点 0，漏掉了末尾的那个 a，返回 0 而正确答案是 1。

二分上界设成 n - 1 后又把返回值写成 right：在 s = "aaa" 这类答案接近上界的用例上，两处边界含义不一致会导致答案差 1，返回值应始终与循环不变量约定的那一侧保持一致。

判定函数里每轮都重建长度为 n 的数组而不是复用预处理结果：s 长度 2000 时二分十一轮各重算一遍前缀哈希，常数被放大十倍以上，容易卡在时间上限。

相似题目

题目	难度	考察点
5. 最长回文子串	中等	同为子串最优长度，但靠中心扩展或 Manacher 而非哈希
28. 找出字符串中第一个匹配项的下标	简单	单模式匹配，滚动哈希与 KMP 两条路线的经典对照
187. 重复的DNA序列	中等	长度固定为 10 不需二分，且要输出全部重复串而非长度
214. 最短回文串	困难	求最长回文前缀，可用正反哈希对比或 KMP 的失配数组
287. 寻找重复数	中等	同样二分答案，判定依据换成小于等于中点的计数
410. 分割数组的最大值	困难	二分答案的判定器是贪心分段，考察上下界的初始化
459. 重复的子字符串	简单	判断整串能否由某个子串循环拼成，可用 `s + s` 技巧一步判定
718. 最长重复子数组	中等	在两个数组之间找公共段，标准解是二维动态规划
875. 爱吃香蕉的珂珂	中等	二分答案的入门题，判定器是一次除法求和
940. 不同的子序列 II	困难	统计去重后的子序列个数，靠按末尾字符归并的递推
1044. 最长重复子串	困难	同一模型放大到三万量级，对哈希碰撞与常数优化的要求更严苛
1143. 最长公共子序列	中等	允许不连续，因此无法用子串指纹，只能走动态规划