滚动哈希在字符串匹配中的应用：Rabin-Karp算法详解

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

核心思路

1. 计算模式串的哈希值
2. 使用滑动窗口计算文本串中每个子串的哈希值
3. 当哈希值匹配时进行精确比较（防止哈希冲突）

详细解题步骤

步骤1：理解滚动哈希原理

• 选择一个大素数p作为模数（如10^9+7）
• 选择基数base（如256，对应ASCII字符集）
• 字符串"abc"的哈希计算：hash = (a×base² + b×base¹ + c×base⁰) mod p
• 关键优势：窗口滑动时可通过增量更新避免重新计算整个哈希

步骤2：预处理计算

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0 or n < m:
        return []
    
    p = 10**9 + 7  # 大素数
    base = 256     # 基数
    results = []

步骤3：计算最高位权重因子

• 计算base^(m-1) mod p，用于滑动时移除最高位字符

    # 计算base^(m-1) mod p
    highest_weight = 1
    for i in range(m-1):
        highest_weight = (highest_weight * base) % p

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

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

步骤5：滑动窗口比较哈希

    for i in range(n - m + 1):
        # 1. 比较哈希值
        if pattern_hash == window_hash:
            # 2. 哈希匹配时进行精确比较（防止冲突）
            if text[i:i+m] == pattern:
                results.append(i)
        
        # 3. 滑动到下一个窗口（避免越界）
        if i < n - m:
            # 移除左边字符，添加右边字符
            window_hash = (window_hash - ord(text[i]) * highest_weight) % p
            window_hash = (window_hash * base + ord(text[i+m])) % p
            # 确保哈希值为非负
            if window_hash < 0:
                window_hash += p
    
    return results

步骤6：处理边界情况

• 空字符串处理：模式串为空时直接返回空结果
• 文本短于模式串：直接返回空结果
• 负数哈希：模运算后可能产生负数，需要调整为正数

算法优化要点

1. 双重哈希：使用两个不同的基数和模数，大幅降低冲突概率
2. 快速模运算：利用位运算优化取模操作
3. 字符映射：可将字符预先映射为数字提升效率

复杂度分析

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

这个算法特别适用于多模式匹配和需要频繁比较相同长度子串的场景，是滚动哈希技术的经典应用。