1044. 最长重复子串

Hard

题目描述

给定一个字符串 s，考虑其所有重复子串：出现 2 次或更多次的 s 的（连续）子串。这些出现的位置可能重叠。

返回任意一个具有最长可能长度的重复子串。如果 s 不含重复子串，则答案为 ""。

示例 1：

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

示例 2：

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

约束条件：

2 <= s.length <= 3 * 10^4
s 由小写英文字母组成。

提示：

对答案的长度进行二分搜索。（如果存在长度为 10 的答案，那么也存在长度为 9、8、7… 的答案）
要检查是否存在长度为 K 的答案，我们可以使用 Rabin-Karp 算法。

解题思路

这道题需要找到最长的重复子串，关键思路是二分搜索 + Rabin-Karp 滚动哈希。

核心思想：

单调性发现：如果存在长度为 k 的重复子串，那么一定存在长度为 k-1, k-2… 的重复子串（通过截取得到）
二分搜索长度：在 [1, n-1] 范围内二分搜索最大的可能长度
Rabin-Karp 验证：对于每个候选长度，用滚动哈希快速检查是否存在重复子串

算法步骤：

二分搜索重复子串的长度，范围是 [0, n-1]
对于每个长度 mid，使用 Rabin-Karp 算法检查是否存在该长度的重复子串
Rabin-Karp 使用多项式哈希，通过滑动窗口在 O(n) 时间内检查所有长度为 mid 的子串
如果找到重复子串，尝试更大的长度；否则尝试更小的长度

优化要点：

使用大质数作为哈希的模数，避免哈希冲突
预计算幂次，避免重复计算
滚动哈希技术保证单次检查的时间复杂度为 O(n)

这种方法比暴力解法效率高很多，特别适合处理长字符串的重复子串问题。

代码实现

class Solution {
public:
    string longestDupSubstring(string s) {
        int n = s.length();
        int left = 0, right = n - 1;
        string result = "";
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            string dup = search(s, mid);
            if (!dup.empty()) {
                result = dup;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
private:
    string search(string& s, int len) {
        if (len == 0) return "";
        
        int n = s.length();
        const long long MOD = 1000000007;
        const long long BASE = 256;
        
        long long hash = 0;
        long long pow = 1;
        
        // Calculate hash for first window and highest power
        for (int i = 0; i < len; i++) {
            hash = (hash * BASE + s[i]) % MOD;
            if (i < len - 1) pow = (pow * BASE) % MOD;
        }
        
        unordered_set<long long> seen;
        seen.insert(hash);
        
        // Rolling hash
        for (int i = len; i < n; i++) {
            hash = (hash - (long long)s[i - len] * pow % MOD + MOD) % MOD;
            hash = (hash * BASE + s[i]) % MOD;
            
            if (seen.count(hash)) {
                return s.substr(i - len + 1, len);
            }
            seen.insert(hash);
        }
        
        return "";
    }
};

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        def search(length):
            if length == 0:
                return ""
            
            MOD = 10**9 + 7
            BASE = 256
            n = len(s)
            
            # Calculate hash for first window
            hash_val = 0
            pow_val = 1
            
            for i in range(length):
                hash_val = (hash_val * BASE + ord(s[i])) % MOD
                if i < length - 1:
                    pow_val = (pow_val * BASE) % MOD
            
            seen = {hash_val}
            
            # Rolling hash
            for i in range(length, n):
                hash_val = (hash_val - ord(s[i - length]) * pow_val) % MOD
                hash_val = (hash_val * BASE + ord(s[i])) % MOD
                
                if hash_val in seen:
                    return s[i - length + 1:i + 1]
                seen.add(hash_val)
            
            return ""
        
        left, right = 0, len(s) - 1
        result = ""
        
        while left <= right:
            mid = (left + right) // 2
            dup = search(mid)
            if dup:
                result = dup
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class Solution {
    public string LongestDupSubstring(string s) {
        int left = 0, right = s.Length - 1;
        string result = "";
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            string dup = Search(s, mid);
            if (!string.IsNullOrEmpty(dup)) {
                result = dup;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    private string Search(string s, int len) {
        if (len == 0) return "";
        
        int n = s.Length;
        const long MOD = 1000000007;
        const long BASE = 256;
        
        long hash = 0;
        long pow = 1;
        
        // Calculate hash for first window
        for (int i = 0; i < len; i++) {
            hash = (hash * BASE + s[i]) % MOD;
            if (i < len - 1) pow = (pow * BASE) % MOD;
        }
        
        HashSet<long> seen = new HashSet<long>();
        seen.Add(hash);
        
        // Rolling hash
        for (int i = len; i < n; i++) {
            hash = (hash - (long)s[i - len] * pow % MOD + MOD) % MOD;
            hash = (hash * BASE + s[i]) % MOD;
            
            if (seen.Contains(hash)) {
                return s.Substring(i - len + 1, len);
            }
            seen.Add(hash);
        }
        
        return "";
    }
}

var longestDupSubstring = function(s) {
    const n = s.length;
    const MOD = 2**63 - 1;
    const BASE = 26;
    
    function search(len) {
        if (len === 0) return "";
        
        let hash = 0;
        let power = 1;
        
        for (let i = 0; i < len; i++) {
            hash = (hash * BASE + (s.charCodeAt(i) - 97)) % MOD;
            if (i < len - 1) power = (power * BASE) % MOD;
        }
        
        const seen = new Set([hash]);
        
        for (let i = len; i < n; i++) {
            hash = (hash - (s.charCodeAt(i - len) - 97) * power % MOD + MOD) % MOD;
            hash = (hash * BASE + (s.charCodeAt(i) - 97)) % MOD;
            
            if (seen.has(hash)) {
                return s.substring(i - len + 1, i + 1);
            }
            seen.add(hash);
        }
        
        return "";
    }
    
    let left = 0, right = n - 1;
    let result = "";
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const found = search(mid);
        
        if (found !== "") {
            result = found;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n log n)	二分搜索 O(log n) 次，每次 Rabin-Karp 检查需要 O(n) 时间
空间复杂度	O(n)	哈希集合存储所有长度为 mid 的子串哈希值，最多 O(n) 个

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析