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

题目描述：
给定一个文本字符串text和一个模式字符串pattern，实现Rabin-Karp算法来查找pattern在text中所有出现的位置。该算法通过滚动哈希的方式，在O(n+m)的平均时间复杂度内完成匹配（n为text长度，m为pattern长度）。

解题过程：

1. 理解核心概念：滚动哈希
   滚动哈希的核心思想是：当我们在文本中滑动窗口时，新窗口的哈希值可以通过旧窗口的哈希值快速计算得出，而不需要重新计算整个窗口的哈希值。

2. 哈希函数设计
   我们使用多项式滚动哈希函数：
   hash(s) = (s[0] × p^(m-1) + s[1] × p^(m-2) + ... + s[m-1] × p^0) mod q
   其中p是质数基数，q是大质数模数。

3. 算法步骤详解：

步骤1：预处理计算

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0 or n < m:
        return []
    
    # 参数设置
    p = 257  # 质数基数
    q = 10**9 + 7  # 大质数模数
    
    # 计算p的最高次幂
    p_power = pow(p, m-1, q)

步骤2：计算模式串和第一个窗口的哈希值

    # 计算模式串的哈希值
    pattern_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * p + ord(pattern[i])) % q
    
    # 计算文本第一个窗口的哈希值
    window_hash = 0
    for i in range(m):
        window_hash = (window_hash * p + ord(text[i])) % q

步骤3：滑动窗口比较

    result = []
    
    # 遍历所有可能的窗口位置
    for i in range(n - m + 1):
        # 哈希值匹配时，进行精确比较（防止哈希冲突）
        if window_hash == pattern_hash:
            if text[i:i+m] == pattern:
                result.append(i)
        
        # 计算下一个窗口的哈希值（滚动哈希）
        if i < n - m:
            # 移除最左边字符的贡献
            window_hash = (window_hash - ord(text[i]) * p_power) % q
            # 确保非负
            window_hash = (window_hash * p + ord(text[i + m])) % q
            # 处理可能的负数
            if window_hash < 0:
                window_hash += q
    
    return result

4. 关键优化点解释：

哈希冲突处理：

• 当哈希值匹配时，必须进行精确的字符串比较
• 这是因为不同的字符串可能产生相同的哈希值（哈希冲突）
• 在实际应用中，通过选择合适的p和q可以最小化冲突概率

滚动哈希的高效性：

• 每次滑动窗口只需要常数时间操作
• 相比重新计算整个窗口的哈希值（O(m)），滚动哈希只需要O(1)

5. 复杂度分析：

• 时间复杂度：平均O(n+m)，最坏O(nm)（当哈希冲突频繁时）
• 空间复杂度：O(1)（除了存储结果）

6. 实际应用示例：

# 测试示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
result = rabin_karp(text, pattern)
print(f"模式出现在位置: {result}")  # 输出: [10]

这个算法特别适合在长文本中搜索多个模式，或者需要处理流式数据的场景，因为它的滚动哈希特性可以高效处理连续的窗口比较。