Rabin-Karp算法在字符串搜索中的应用：滚动哈希实现高效模式匹配

题目描述：给定一个文本字符串text和一个模式字符串pattern，使用Rabin-Karp算法在text中查找pattern的所有出现位置。要求实现滚动哈希机制，通过哈希值的快速更新来高效完成搜索。

解题过程：

1. 基本思路分析
   Rabin-Karp算法的核心思想是：计算模式字符串的哈希值，然后计算文本中每个可能与模式匹配的子串的哈希值。如果哈希值匹配，再进一步验证字符是否真正匹配，避免哈希冲突导致的误判。

2. 哈希函数设计
   我们使用多项式滚动哈希函数，这是Rabin-Karp算法的关键：

• 选择一个质数基数（通常为31、101或257）
• 计算哈希值：hash = (c₁ × base^(m-1) + c₂ × base^(m-2) + ... + c_m) mod prime
• 其中m是模式长度，c_i是字符的整数值（如ASCII码）

3. 预处理阶段

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    
    base = 31  # 哈希基数
    prime = 10**9 + 7  # 大质数减少冲突
    
    # 计算base^(m-1) mod prime
    highest_power = 1
    for i in range(m-1):
        highest_power = (highest_power * base) % prime

4. 计算模式字符串的哈希值

    pattern_hash = 0
    for char in pattern:
        pattern_hash = (pattern_hash * base + ord(char)) % prime

5. 计算文本第一个窗口的哈希值

    window_hash = 0
    for i in range(m):
        window_hash = (window_hash * base + ord(text[i])) % prime

6. 滚动哈希机制实现
   这是算法的核心优化部分，通过数学运算在O(1)时间内更新哈希值：

    results = []
    
    # 检查第一个窗口
    if window_hash == pattern_hash:
        if text[:m] == pattern:
            results.append(0)
    
    # 滑动窗口，使用滚动哈希
    for i in range(1, n - m + 1):
        # 移除离开窗口的字符贡献
        leaving_char = ord(text[i-1])
        # 添加新进入窗口的字符贡献
        new_char = ord(text[i+m-1])
        
        # 滚动哈希计算：新哈希 = (旧哈希 - 离开字符×最高幂次)×基数 + 新字符
        window_hash = (window_hash - leaving_char * highest_power) % prime
        window_hash = (window_hash * base + new_char) % prime
        
        # 处理可能的负值
        if window_hash < 0:
            window_hash += prime

7. 哈希冲突处理
   由于哈希可能冲突，需要验证实际匹配：

        if window_hash == pattern_hash:
            # 验证实际字符匹配，避免哈希冲突
            if text[i:i+m] == pattern:
                results.append(i)

8. 完整算法实现

def rabin_karp_complete(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    
    base = 31
    prime = 10**9 + 7
    
    # 预计算最高幂次
    highest_power = 1
    for i in range(m-1):
        highest_power = (highest_power * base) % prime
    
    # 计算模式哈希
    pattern_hash = 0
    for char in pattern:
        pattern_hash = (pattern_hash * base + ord(char)) % prime
    
    # 初始化窗口哈希
    window_hash = 0
    for i in range(m):
        window_hash = (window_hash * base + ord(text[i])) % prime
    
    results = []
    
    # 检查所有窗口
    for i in range(n - m + 1):
        if window_hash == pattern_hash:
            if text[i:i+m] == pattern:
                results.append(i)
        
        # 更新下一个窗口的哈希（避免最后一个窗口后越界）
        if i < n - m:
            window_hash = (window_hash - ord(text[i]) * highest_power) % prime
            window_hash = (window_hash * base + ord(text[i+m])) % prime
            if window_hash < 0:
                window_hash += prime
    
    return results

9. 算法复杂度分析

• 时间复杂度：平均O(n+m)，最坏O(n×m)
• 空间复杂度：O(1)（不考虑结果存储）
• 滚动哈希使得每次窗口移动的哈希计算为O(1)时间

10. 实际应用优化

• 使用双重哈希减少冲突概率
• 对于大文本，可以分段处理
• 结合其他算法（如KMP）处理最坏情况

这个算法特别适合在长文本中搜索多个模式，或者用于 plagiarism检测、DNA序列匹配等场景。