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

Categories:

题目描述
思路分析
1. 解法一：二分长度 + 滚动哈希（推荐）
相似题目

题目描述

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

思路分析

解法一：二分长度 + 滚动哈希（推荐）

核心思路：

对答案长度进行二分，判断是否存在重复子串。

使用滚动哈希快速计算所有长度为 L 的子串哈希。

若某个哈希值重复出现，则说明存在重复子串。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示字符串长度。

空间复杂度：O(n)，存储哈希集合。

import java.util.*;

class Solution {
    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 {
    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
}

相似题目

题目	难度	考察点
1044. 最长重复子串	困难	二分 + 哈希
1392. 最长快乐前缀	困难	哈希
1062. 最长重复子串的长度	中等	二分
3. 无重复字符的最长子串	中等	滑动窗口
187. 重复的DNA序列	中等	哈希

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/45409762