#1044. 最长重复子串

• LeetCode：1044. 最长重复子串
• 难度：困难
• 归类：字符串、二分答案、滚动哈希、后缀数组
• 主解法：二分重复子串长度 + Rabin–Karp 滚动哈希

#先给结论

直接枚举所有子串是平方级候选，关键转折是把最优化问题拆成判定问题：

长度为 length 的子串是否至少出现两次？

这个判定具有单调性：长度 length 可行，则所有更短长度都可行（取两次出现的相同前缀即可）；长度 length 不可行，则更长长度也不可行。因此可以二分最大可行长度。

对每个固定长度，用滚动哈希在线性时间内扫描全部定长窗口；哈希相同后再逐字符比较，排除哈希碰撞。

一句话记忆：二分长度，滚动窗口算哈希，哈希相等后校验真实字符。

#题目描述

给定字符串 s，找出任意一个最长重复子串。重复子串必须是连续的，并且在 s 中至少出现两次；两次出现可以重叠。

示例 1：

输入：s = "banana"
输出："ana"

"ana" 分别从下标 1 和 3 开始，两次出现有重叠，这是合法的。

示例 2：

输入：s = "abcd"
输出：""

题目约束：

• 2 <= s.length <= 3 × 10^4。
• s 只包含小写英文字母。
• 如果有多个最长答案，返回任意一个即可。

#核心思路：二分答案长度

#为什么判定可以二分

定义判定命题：

P(length) = 是否存在长度为 length 的重复子串

它具有前缀单调性：

P(0), P(1), ..., P(answer) 为 true
P(answer + 1), ..., P(n - 1) 为 false

• 长度可行 → 更短必可行：取两次出现的相同前缀，就是更短的重复子串。
• 长度不可行 → 更长必不可行：更长重复子串的长度 length 前缀会构成反例。

所以要找的是最后一个使 P(length) 为真的长度，这正是二分答案的标准形态。

注意本题不是"左右指针按窗口合法性伸缩"的典型滑动窗口。固定长度后，候选确实是依次右移一位的定长窗口，但让搜索范围减半的是答案长度的单调性，而不是窗口伸缩。

#二分区间如何收缩

使用闭区间 [left, right]：

• left / right：尚未排除的最小、最大候选长度。
• bestLength / bestStart：已确认存在重复子串的最大长度及某次出现的起点。

最长重复子串不可能等于整个字符串（长度 n 只有一个起点），所以初始区间为 [1, n - 1]；长度 0 对应默认答案 ""，不参与搜索。

每轮检查 mid：

• 可行：记录 bestLength = mid、bestStart = 当前重复窗口起点，然后 left = mid + 1，继续找更长的。
• 不可行：right = mid - 1，由单调性排除 mid 及所有更长长度。

二分结束后返回 s.slice(bestStart, bestStart + bestLength)；若没有任何非空重复子串，bestLength 保持 0，自然返回 ""。

#定长判定：滚动哈希 + 精确比较

findDuplicateStart(length) 要回答"长度为 length 的子串是否出现两次"。朴素做法是把每个窗口字符串存入集合，但窗口内容比较和存储都是 O(length)。滚动哈希把窗口压成一个整数，每次右移只做常数次算术。

#多项式哈希

字符编码为 1～26，以 BASE = 27 构造长度为 length 的窗口哈希：

H = c₀ × BASE^(length - 1)
  + c₁ × BASE^(length - 2)
  + ...
  + c_(length - 1)

所有运算对 MOD 取模。窗口从起点 start - 1 右移到 start 时：

1. 减去离开窗口的字符乘以 BASE^(length - 1)（最高位贡献）。
2. 将剩余哈希乘以 BASE，相当于整体左移一位。
3. 加上新进入窗口的字符。

#哈希碰撞必须校验真实内容

内容相同的窗口哈希一定相同，但哈希相同不代表内容相同——取模必然存在碰撞。因此哈希表不能只记录"这个哈希出现过"，而要保存该哈希对应的所有历史起点：

1. 当前窗口命中某个哈希桶时，逐个与桶内历史窗口逐字符比较。
2. 找到完全相同的窗口，返回当前起点。
3. 全部不同则说明只是碰撞，把当前起点也加入该桶。

只有精确比较通过后才能更新 bestStart / bestLength，否则可能把碰撞当成答案。这一步使结果不依赖"哈希绝不碰撞"的假设。

#示例推演

以 s = "banana" 为例，n = 6：

搜索结束，最长重复子串长度为 3，返回 "ana"。

#代码实现

思路参考：JoshCrozier/leetcode-javascript。本文重新整理了二分状态和滚动窗口，并保留哈希碰撞后的精确比较；原项目采用 MIT License。

#JavaScript 实现

/**
 * @param {string} s
 * @return {string}
 */
var longestDupSubstring = function (s) {
    const MOD = 1_000_000_007;
    // 字符编码为 1~26，多项式哈希的基数取大于字母表的最小整数
    const BASE = 27;
    const n = s.length;

    // 把字符预编码成数字，滚动计算和逐字符比较都直接读数组
    const codes = new Uint8Array(n);

    for (let i = 0; i < n; i++) {
        codes[i] = s.charCodeAt(i) - 96;
    }

    // 二分答案长度，闭区间 [left, right]
    // 最长重复子串不可能是整个字符串，所以上界是 n - 1
    let left = 1;
    let right = n - 1;

    // 已确认可行的最大长度，以及该重复子串某次出现的起点
    let bestStart = 0;
    let bestLength = 0;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        // 判定问题：长度为 mid 的子串是否至少出现两次
        const start = findDuplicateStart(mid);

        if (start !== -1) {
            // 可行：记录答案，继续向右找更长的
            bestStart = start;
            bestLength = mid;
            left = mid + 1;
        } else {
            // 不可行：由单调性排除 mid 及所有更长长度
            right = mid - 1;
        }
    }

    // bestLength 保持 0 时，slice(0, 0) 自然返回 ""
    return s.slice(bestStart, bestStart + bestLength);

    // 存在长度为 length 的重复子串时返回某次出现的起点，否则返回 -1
    function findDuplicateStart(length) {
        // 移出窗口的字符权重：BASE^(length - 1)
        let highestPower = 1;
        let hash = 0;

        for (let i = 1; i < length; i++) {
            highestPower = (highestPower * BASE) % MOD;
        }

        // 初始窗口 [0, length) 的完整多项式哈希
        for (let i = 0; i < length; i++) {
            hash = (hash * BASE + codes[i]) % MOD;
        }

        // 哈希值 -> 具有该哈希的所有历史窗口起点
        // 必须存数组：同哈希可能只是碰撞，不能覆盖或丢弃
        const startsByHash = new Map();
        startsByHash.set(hash, [0]);

        // 窗口逐个右移一位，滚动更新哈希
        for (let start = 1; start + length <= n; start++) {
            const outgoing = codes[start - 1];
            const incoming = codes[start + length - 1];

            // 第一步：减去离开字符的最高位贡献
            // JS 的 % 可能为负，先加 MOD 再取模
            hash =
                (hash - (outgoing * highestPower) % MOD + MOD) % MOD;
            // 第二步：剩余部分乘 BASE 左移一位；第三步：加入新字符
            hash = (hash * BASE + incoming) % MOD;

            const previousStarts = startsByHash.get(hash);

            if (previousStarts) {
                // 哈希命中：逐字符校验，排除碰撞，相同才算真的重复
                for (const previousStart of previousStarts) {
                    if (sameSubstring(previousStart, start, length)) {
                        return start;
                    }
                }
                // 只是碰撞：把当前起点也存入该桶，供后续窗口比较
                previousStarts.push(start);
            } else {
                startsByHash.set(hash, [start]);
            }
        }

        return -1;
    }

    // 逐字符比较两个起点开始、长度为 length 的子串是否完全相同
    function sameSubstring(first, second, length) {
        for (let offset = 0; offset < length; offset++) {
            if (codes[first + offset] !== codes[second + offset]) {
                return false;
            }
        }
        return true;
    }
};

MOD 以内的哈希值与 BASE = 27 相乘后仍远小于 JavaScript 的最大安全整数 2^53 - 1，所以上述乘法不会先发生整数精度丢失。

#代码与思路对照

#正确性说明

#定长判定正确

findDuplicateStart(length) 按起点顺序扫描每个长度为 length 的窗口。滚动公式与完整多项式哈希等价，所以同一内容的窗口必然进入同一个哈希桶。

当当前窗口与桶内某个历史窗口逐字符相等时，它们起点不同且内容完全相同，确实找到了重复子串，不会误报。反过来，任意出现至少两次的长度 length 子串，其后一次出现被扫描时，一定能在对应哈希桶中找到前一次起点并通过逐字符比较，不会漏报。

#二分查找正确

由前缀单调性，可行长度构成连续前缀区间。二分在可行时向右搜索、不可行时向左搜索，最终记录的 bestLength 就是最大可行长度，返回的子串即最长重复子串。

#边界与陷阱

• 没有重复字符： "abcd" 应返回 ""。
• 全部相同： "aaaaa" 的答案是 "aaaa"，两次出现允许重叠。
• 最短输入： "aa" 返回 "a"，"ab" 返回 ""。
• 多个最长答案： 题目允许返回任意一个，不需要比较字典序。
• 搜索上界： 最长重复子串至多为 n - 1。
• 二分方向： 找到重复子串后要搜索更长长度，即 left = mid + 1。
• 最高次幂： 移出窗口的字符权重是 BASE^(length - 1)，不是 BASE^length。
• 模减法： JavaScript 的 % 可能保留负号，减去旧字符后要先加 MOD 再取模。
• 重叠出现： 不要额外要求两个起点之差大于等于子串长度。
• 碰撞处理： 不能只用 Set 保存哈希并直接返回；必须校验真实内容，或者明确接受概率正确的双哈希方案。

#复杂度分析

设 n = s.length。

在没有意外哈希碰撞，或者把哈希操作视为期望常数时间时：

• 每次定长检查扫描 O(n) 个窗口。
• 二分执行 O(log n) 次检查。
• 期望时间复杂度为 O(n log n)。
• 空间复杂度为 O(n)，用于字符编码、哈希表和窗口起点。

精确字符比较保证了答案一定正确，但也意味着最坏时间不能无条件写成 O(n log n)。对某个长度 length，设相同哈希桶内实际执行的字符比较总成本为 C_length，则总时间更准确地写成：

O(n log n + Σ C_length)

如果人为构造大量哈希碰撞，同一轮可能比较平方级窗口对，每次又最多比较 O(n) 个字符，保守的确定性最坏上界会明显高于 O(n log n)。实际题目中单个大质数哈希通常可以通过；若需要更稳定的性能，可以使用双哈希降低碰撞概率，或改用确定性的后缀数组。

#替代解法

#双滚动哈希

同时维护两组不同模数的哈希，只有两个哈希都相同时才认为是候选。碰撞概率会大幅降低，通常可以省略逐字符比较并获得期望 O(n log n) 时间，但理论上仍然是概率算法。

#后缀数组

把所有后缀排序后，任意重复子串一定是某两个后缀的公共前缀；最长重复子串就是相邻后缀的最大最长公共前缀。

• 使用倍增法和比较排序构建后缀数组，通常为 O(n log² n)。
• 使用基数排序优化倍增过程可以达到 O(n log n)。
• 构建后缀数组后，Kasai 算法可在 O(n) 时间计算 LCP 数组。

这种方案确定性更强，但实现长度和调试成本都高于二分加滚动哈希。

#后缀自动机

后缀自动机也能在线性状态规模内统计子串出现次数，并找出最长重复子串。渐进复杂度优秀，但状态构建、出现次数传播和答案恢复更复杂，通常不作为面试中的第一实现。

#面试官递进追问

#1. 为什么可以二分答案长度？

因为“存在长度为 length 的重复子串”具有前缀单调性：可行长度的所有更短长度都可行，不可行长度的所有更长长度都不可行。

#2. 为什么最长重复子串长度最多是n - 1？

长度为 n 的子串只有整个字符串一个起点，不可能出现两次；长度 n - 1 则可能在全相同字符串中从起点 0 和 1 重叠出现。

#3. 滚动哈希为什么能把每次窗口移动降为常数操作？

新旧窗口的大部分字符相同。减去旧首字符的最高位贡献，将剩余部分乘以基数，再加入新尾字符，就能从旧哈希得到新哈希。

#4. 为什么相同哈希后还要比较真实字符？

取模会把大量不同字符串映射到有限的哈希值，理论上必然存在碰撞。真实字符比较可以排除碰撞，使算法不会返回内容不同的两个窗口。

#5. 为什么哈希表要保存起点数组，而不是每个哈希只保存一个起点？

某个历史起点可能只是与当前窗口发生哈希碰撞。如果比较失败就覆盖或丢弃其他起点，之后可能漏掉同一哈希桶中真正相同的窗口。

#6. 两次出现重叠会影响算法吗？

不会。题目允许重叠，算法只要求两个起点不同，不限制它们的距离。例如 "aaaaa" 中起点 0 和 1 的 "aaaa" 就是合法答案。

#7. 这份实现为什么只能说期望O(n log n)？

滚动计算本身是线性的，但碰撞桶中的逐字符校验可能产生额外成本。正常哈希分布下碰撞很少，时间接近 O(n log n)；极端碰撞下会退化。

#8. 什么时候应该改用后缀数组？

当题目要求确定性的复杂度保证、需要回答多次后缀或公共前缀查询，或者输入可能针对固定哈希构造时，后缀数组更合适；代价是实现明显更复杂。

#常见错误

• 没有证明长度判定的单调性就直接套二分。
• 把本题当成普通可变长度滑动窗口。
• 找到可行长度后向左搜索，二分方向写反。
• 只保存哈希值，不处理碰撞，导致概率性错误答案。
• 哈希碰撞后只比较一个历史起点，可能漏掉桶内真正重复的窗口。
• 忘记滚动哈希移出的字符权重是 BASE^(length - 1)。
• 禁止重复子串重叠，错误排除 "aaaaa" 的答案 "aaaa"。
• 复杂度只根据二分层数写成 O(log n)，或者忽略碰撞校验直接宣称确定性的 O(n log n)。

#可迁移总结

• 二分答案： 当可行性随答案大小呈单调变化时，可以二分最后一个可行值。
• 定长窗口： 固定长度后，滚动哈希能复用相邻窗口的大部分计算。
• 哈希只负责筛选： 单哈希相等是候选关系，不是字符串相等的证明。
• 一句话记忆： 二分长度，滚动窗口算哈希，哈希相等后校验真实字符。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 为什么长度 5 可行时，长度 1～4 一定都可行？

2. 在 "aaaaa" 中，为什么长度 4 的答案不违反“两次出现”的要求？

3. 如果哈希相等后不比较真实字符，算法的正确性证明缺少哪一步？

4. 尝试写出长度为 length 时，从窗口起点 i - 1 滚动到 i 的哈希公式。