LeetCode 1044. 最长重复子串

Categories:

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

题目描述

✅ 1044. 最长重复子串

思路分析

解法一：二分 + Rabin-Karp 滚动哈希（推荐）

核心思路：

对子串长度进行二分：若长度为 mid 的重复子串存在，则更短的也一定存在，满足单调性。

对于给定长度 mid，用 Rabin-Karp 滚动哈希在 O(n) 时间内枚举所有长度为 mid 的子串，将其哈希值存入哈希集合，若出现重复则说明存在长度为 mid 的重复子串。

为降低哈希碰撞概率，使用双哈希（两个不同的模数）或选取足够大的模数。

二分范围是 [1, n-1]（长度至少为 1，至多为 n-1，因为子串本身不算重复）。

最终二分收敛后，再用哈希检查一次最大合法长度，记录对应子串。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示字符串长度，二分 O(log n) 次，每次滚动哈希检查 O(n)。

空间复杂度：O(n)，其中 n 表示哈希集合最多存储 n 个哈希值。

class Solution {
    // 模数与基数，选用大质数降低碰撞概率
    private static final long MOD = 1_000_000_007L;
    private static final long BASE = 31L;

    public String longestDupSubstring(String s) {
        int n = s.length();
        // 将字符映射为 1~26 的整数，避免 0 造成误判
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.charAt(i) - 'a' + 1;
        }

        // 二分子串长度
        int lo = 1, hi = n - 1;
        String result = "";
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            String dup = check(arr, s, mid);
            if (dup != null) {
                // 找到重复子串，尝试更长
                result = dup;
                lo = mid + 1;
            } else {
                // 未找到，缩短长度
                hi = mid - 1;
            }
        }
        return result;
    }

    // 用滚动哈希检查是否存在长度为 len 的重复子串
    private String check(int[] arr, String s, int len) {
        int n = arr.length;
        // 计算最高位的幂次 BASE^(len-1) % MOD
        long power = 1L;
        for (int i = 0; i < len - 1; i++) {
            power = power * BASE % MOD;
        }
        // 计算第一个窗口的哈希值
        long hash = 0L;
        for (int i = 0; i < len; i++) {
            hash = (hash * BASE + arr[i]) % MOD;
        }
        // 存储已出现的哈希值及对应起始索引（用于碰撞验证）
        Map<Long, List<Integer>> seen = new HashMap<>();
        seen.put(hash, new ArrayList<>(List.of(0)));

        // 滑动窗口滚动哈希
        for (int i = 1; i + len - 1 < n; i++) {
            // 移除最左字符，加入最右字符
            hash = (hash - arr[i - 1] * power % MOD + MOD) % MOD;
            hash = (hash * BASE + arr[i + len - 1]) % MOD;
            if (seen.containsKey(hash)) {
                // 哈希碰撞验证：逐字符比较
                String cur = s.substring(i, i + len);
                for (int start : seen.get(hash)) {
                    if (s.substring(start, start + len).equals(cur)) {
                        return cur;
                    }
                }
                seen.get(hash).add(i);
            } else {
                seen.put(hash, new ArrayList<>(List.of(i)));
            }
        }
        return null;
    }
}

func longestDupSubstring(s string) string {
	n := len(s)
	// 将字符映射为 1~26 的整数，避免 0 造成误判
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = int(s[i]-'a') + 1
	}

	const mod = 1_000_000_007
	const base = 31

	// check 检查是否存在长度为 length 的重复子串，返回该子串或空串
	check := func(length int) string {
		// 计算最高位幂次 base^(length-1) % mod
		power := 1
		for i := 0; i < length-1; i++ {
			power = power * base % mod
		}
		// 计算首个窗口哈希值
		h := 0
		for i := 0; i < length; i++ {
			h = (h*base + arr[i]) % mod
		}
		// 记录哈希值到起始索引列表的映射，用于碰撞验证
		seen := map[int][]int{h: {0}}
		for i := 1; i+length-1 < n; i++ {
			// 滚动：移除最左字符，加入最右字符
			h = (h - arr[i-1]*power%mod + mod) % mod
			h = (h*base + arr[i+length-1]) % mod
			if starts, ok := seen[h]; ok {
				cur := s[i : i+length]
				// 碰撞验证：逐字符比较
				for _, start := range starts {
					if s[start:start+length] == cur {
						return cur
					}
				}
				seen[h] = append(seen[h], i)
			} else {
				seen[h] = []int{i}
			}
		}
		return ""
	}

	// 二分子串长度
	lo, hi := 1, n-1
	result := ""
	for lo <= hi {
		mid := lo + (hi-lo)/2
		dup := check(mid)
		if dup != "" {
			// 找到重复子串，尝试更长
			result = dup
			lo = mid + 1
		} else {
			// 未找到，缩短长度
			hi = mid - 1
		}
	}
	return result
}

相似题目

题目	难度	考察点
187. 重复的DNA序列	中等	滑动窗口、滚动哈希
718. 最长重复子数组	中等	动态规划、二分+哈希
686. 重复叠加字符串匹配	中等	字符串匹配
459. 重复的子字符串	简单	KMP、字符串
1062. 最长重复子串	中等	二分、滚动哈希
28. 找出字符串中第一个匹配项的下标	简单	KMP、字符串匹配

本文作者: HGNULB

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