Rabin-Karp算法在滚动哈希中的应用：重复子串查找

题目描述：给定一个字符串s，找出其中至少出现两次的最长子串。如果有多个这样的子串，返回任意一个即可。要求使用Rabin-Karp算法通过滚动哈希高效解决。

解题过程：

1. 问题分析

• 我们需要找到字符串s中重复出现的最长子串
• 暴力解法需要枚举所有子串O(n²)，然后比较每个子串是否重复出现O(n)，总复杂度O(n³)
• 使用哈希表存储子串可以优化到O(n²)，但空间复杂度较高
• Rabin-Karp算法通过滚动哈希可以在O(1)时间内计算子串哈希值

2. Rabin-Karp滚动哈希原理

• 将字符串视为基数为BASE的多项式：s[0]×BASE^(L-1) + s[1]×BASE^(L-2) + ... + s[L-1]×BASE^0
• 使用模运算防止溢出：MOD取一个大质数
• 关键技巧：当窗口向右滑动时，新哈希值 = (旧哈希值 - s[i]×BASE^(L-1))×BASE + s[i+L]

3. 二分查找优化

• 最长重复子串长度满足单调性：如果长度L存在重复子串，那么更短的子串也一定存在
• 使用二分查找确定最大长度：left = 0, right = n-1
• 对每个候选长度mid，检查是否存在重复子串

4. 具体实现步骤

function longestRepeatingSubstring(s):
    n = len(s)
    left, right = 0, n-1
    result = ""
    
    while left <= right:
        mid = (left + right) // 2
        found = checkLength(s, mid)
        
        if found != "":
            result = found
            left = mid + 1  # 尝试更长的子串
        else:
            right = mid - 1  # 缩短子串长度
    
    return result

function checkLength(s, L):
    if L == 0: return ""
    
    BASE = 26  # 小写字母基数
    MOD = 10**9 + 7  # 大质数模数
    n = len(s)
    
    # 计算BASE^L % MOD
    power = 1
    for i in range(L-1):
        power = (power * BASE) % MOD
    
    # 计算第一个长度为L的子串哈希值
    hash_val = 0
    for i in range(L):
        hash_val = (hash_val * BASE + (ord(s[i]) - ord('a'))) % MOD
    
    seen = {hash_val: 0}  # 存储哈希值和起始位置
    
    # 滚动哈希检查所有长度为L的子串
    for i in range(1, n - L + 1):
        # 移除最左边的字符，添加最右边的字符
        hash_val = (hash_val - (ord(s[i-1]) - ord('a')) * power) % MOD
        hash_val = (hash_val * BASE + (ord(s[i+L-1]) - ord('a'))) % MOD
        
        # 处理负数
        if hash_val < 0:
            hash_val += MOD
        
        # 检查是否重复
        if hash_val in seen:
            # 验证是否真正匹配（防止哈希冲突）
            start = seen[hash_val]
            if s[start:start+L] == s[i:i+L]:
                return s[i:i+L]
        else:
            seen[hash_val] = i
    
    return ""

5. 复杂度分析

• 时间复杂度：O(n log n)，二分查找O(log n)次，每次检查O(n)
• 空间复杂度：O(n)，存储哈希值和位置映射
• 相比暴力解法的O(n³)有显著优化

6. 哈希冲突处理

• 虽然概率很低，但不同字符串可能产生相同哈希值
• 当哈希值匹配时，需要实际比较字符串内容确认
• 可以使用双重哈希（两个不同的MOD）进一步降低冲突概率

这个算法展示了滚动哈希在字符串匹配中的高效应用，通过巧妙的哈希计算和滑动窗口技术，将复杂度从O(n³)优化到O(n log n)。