第 82 课·字符串算法进阶

Rabin-Karp 滚动哈希

rabin-karprolling-hashhashmatch

第82课 - Rabin-Karp 滚动哈希

学习目标

  1. 理解滚动哈希的核心思想 - 掌握如何高效计算子串的哈希值
  2. 实现 Rabin-Karp 算法 - 使用滚动哈希进行字符串匹配
  3. 分析算法复杂度 - 理解时间复杂度和哈希冲突的处理
  4. 应用 Rabin-Karp 解决实际问题 - 如多个模式串匹配、重复子串查找等

核心概念

什么是滚动哈希？

想象你在看一列火车车厢，每节车厢上都写着一个数字。如果要计算连续3节车厢的数字总和，传统方法是每次都要重新计算3个数字的和。但滚动哈希的方法很巧妙：当你从第一节车厢移动到第二节时，减去第一节车厢的数字，加上第四节车厢的数字，就得到了新的总和！

在字符串匹配中，我们将每个字符转换成数字，然后用一个"哈希函数"计算字符串的"指纹"。滚动哈希的关键优势在于：当我们移动到下一个子串时，可以O(1)时间计算出新的哈希值，而不需要重新计算整个子串。

Rabin-Karp 算法的工作流程

  1. 计算模式串的哈希值 - 作为"目标指纹"
  2. 计算第一个子串的哈希值 - 与文本串开头长度相同的子串
  3. 滚动比较 - 将哈希值右移一位，快速计算下一个子串的哈希值
  4. 处理哈希冲突 - 当哈希值相同时，再进行逐个字符比较

哈希函数设计

最常用的哈希函数是多项式哈希（Polynomial Rolling Hash）：

哈希值 = (字符1 × base^(n-1) + 字符2 × base^(n-2) + ... + 字符n × base^0) mod mod

其中：

  • base：通常选择一个质数（如31、101、256等）
  • mod：一个大的质数，防止整数溢出（如1e9+7）

代码示例

完整实现：Rabin-Karp 字符串匹配

def rabin_karp_search(text, pattern):
    """
    使用 Rabin-Karp 算法在文本中查找模式串
    
    参数:
    text: 文本字符串
    pattern: 模式字符串
    
    返回:
    所有匹配位置的索引列表
    """
    n = len(text)
    m = len(pattern)
    results = []
    
    # 如果模式串比文本串长，直接返回空
    if m > n:
        return results
    
    # 哈希参数
    base = 31  # 基数，选择一个质数
    mod = 10**9 + 7  # 大的质数模数，防止溢出
    
    # 预计算 base^(m-1) % mod，用于后面滚动哈希
    base_m_minus_1 = pow(base, m - 1, mod)
    
    # 计算模式串的哈希值
    pattern_hash = 0
    for char in pattern:
        pattern_hash = (pattern_hash * base + ord(char)) % mod
    
    # 计算第一个窗口的哈希值
    current_hash = 0
    for i in range(m):
        current_hash = (current_hash * base + ord(text[i])) % mod
    
    # 滑动窗口检查每个位置
    for i in range(n - m + 1):
        # 哈希值匹配时，进行逐个字符比较
        if current_hash == pattern_hash:
            # 检查是否是真正的匹配（处理哈希冲突）
            if text[i:i + m] == pattern:
                results.append(i)
        
        # 计算下一个窗口的哈希值（滚动哈希）
        if i < n - m:
            # 移除最左边的字符，添加最右边的新字符
            current_hash = (current_hash - ord(text[i]) * base_m_minus_1) % mod
            current_hash = (current_hash * base + ord(text[i + m])) % mod
            # 确保结果为非负数
            if current_hash < 0:
                current_hash += mod
    
    return results

# 测试代码
if __name__ == "__main__":
    # 测试示例1：基本匹配
    text = "ABABDABACDABABCABAB"
    pattern = "ABAB"
    print(f"文本: {text}")
    print(f"模式: {pattern}")
    print(f"匹配位置: {rabin_karp_search(text, pattern)}")
    # 预期输出: [0, 10, 15]
    
    # 测试示例2：重叠匹配
    text2 = "AAAA"
    pattern2 = "AA"
    print(f"\n文本: {text2}")
    print(f"模式: {pattern2}")
    print(f"匹配位置: {rabin_karp_search(text2, pattern2)}")
    # 预期输出: [0, 1, 2]
    
    # 测试示例3：没有匹配
    text3 = "ABCDEFG"
    pattern3 = "XYZ"
    print(f"\n文本: {text3}")
    print(f"模式: {pattern3}")
    print(f"匹配位置: {rabin_karp_search(text3, pattern3)}")
    # 预期输出: []

代码解释

  1. 初始化阶段：

    • 计算模式串长度和文本长度
    • 设置哈希参数 base 和 mod

  2. 预计算：

    • base_m_minus_1 保存 base^(m-1) % mod，用于滚动哈希时移除最左边字符

  3. 计算哈希值：

    • 计算模式串的哈希值 pattern_hash
    • 计算文本第一个窗口的哈希值 current_hash

  4. 滑动窗口匹配：

    • 对于每个位置，先比较哈希值
    • 如果哈希匹配，再验证实际字符串
    • 使用滚动哈希公式快速计算下一个窗口的哈希值

实践练习

练习1：基础匹配

要求：实现 Rabin-Karp 算法，在文本 "AABAACAADAABAABA" 中查找模式串 "AABA" 的所有出现位置。

预期输出：[0, 9, 12]

提示：注意重叠匹配的情况。

练习2：多模式匹配

要求：修改 Rabin-Karp 算法，同时查找多个模式串。给定文本 "ABCABCDABCD" 和模式串列表 ["ABCD", "AB"], 返回每个模式串的匹配位置。

预期输出：

模式 'ABCD' 在位置 [3, 7]
模式 'AB' 在位置 [0, 4, 8]

练习3：优化滚动哈希

要求：在 Rabin-Karp 算法中，当哈希值匹配时，有时会进行不必要的字符串比较。优化算法，添加"二次哈希"机制来减少冲突。使用两个不同的哈希函数（不同的base和mod），只有当两个哈希都匹配时才进行字符串比较。

预期输出：与基本 Rabin-Karp 相同，但减少假阳性比较。

常见错误

1. 哈希溢出问题

错误：没有正确处理模运算，导致整数溢出或结果为负数。

正确做法：

# 每次运算后都取模，并确保结果为非负数
current_hash = (current_hash - ord(text[i]) * base_m_minus_1) % mod
if current_hash < 0:
    current_hash += mod

2. 边界条件处理错误

错误：没有检查模式串长度是否大于文本长度，导致索引越界。

正确做法：

if m > n:
    return []  # 模式串比文本串长，直接返回空

3. 哈希冲突误判

错误：哈希值相同时就认为匹配成功，没有进行实际字符串比较。

正确做法：哈希值只是快速筛选，必须验证实际字符串：

if current_hash == pattern_hash:
    if text[i:i + m] == pattern:  # 必须验证
        results.append(i)

4. 滚动哈希公式错误

错误：计算下一个哈希值时，公式使用错误。

正确滚动哈希公式：

new_hash = (old_hash - left_char * base^(m-1)) * base + right_char

在代码中体现为：

current_hash = (current_hash - ord(text[i]) * base_m_minus_1) % mod
current_hash = (current_hash * base + ord(text[i + m])) % mod

5. 模数选择不当

错误：选择太小的模数，导致哈希冲突频繁。

建议：选择一个大质数，如 10^9 + 7 或 10^9 + 9。

小结

关键要点回顾

  1. 滚动哈希的核心思想：利用数学公式，O(1) 时间计算相邻子串的哈希值

    • 新哈希 = (旧哈希 - 最左字符 × base^(m-1)) × base + 最右字符

  2. Rabin-Karp 算法流程：

    • 预计算模式串哈希值
    • 滑动窗口，滚动计算每个窗口的哈希值
    • 哈希匹配时验证实际字符串（处理冲突）

  3. 时间复杂度：

    • 最佳情况：O(n + m) - 当哈希冲突很少时
    • 最坏情况：O(n × m) - 当哈希冲突频繁时（实际应用中很少发生）

  4. 应用场景：

    • 多模式串匹配
    • 查找重复子串
    • 文档相似度检测

  5. 优势与局限：

    • ✅ 优势：平均情况下非常高效，特别适合多模式匹配
    • ❌ 局限：哈希冲突会影响性能，需要合理选择哈希参数

下一步学习建议

在掌握了 Rabin-Karp 算法后，建议学习：

  1. KMP 算法（上一课）：确定性的 O(n+m) 匹配算法
  2. AC 自动机（下一课）：多模式匹配的终极解决方案
  3. 后缀数组：更强大的字符串处理数据结构

实战小贴士

  • 在实际工程中，Rabin-Karp 常用于多模式匹配和近似匹配
  • 对于英语文本，base 可选择 31 或 37
  • 如果处理的是 ASCII 字符，base 可以选择 256
  • 在实现时，可以预计算所有 base^i % mod 的值以提高效率
# 练习预计算示例
def precompute_powers(base, mod, max_power):
    powers = [0] * (max_power + 1)
    powers[0] = 1
    for i in range(1, max_power + 1):
        powers[i] = (powers[i-1] * base) % mod
    return powers

通过本课的学习，你应该已经掌握了 Rabin-Karp 算法和滚动哈希的核心思想。这种算法虽然在理论上有哈希冲突的风险，但在实际应用中表现优秀，特别是需要同时匹配多个模式串时。继续练习并尝试解决更复杂的字符串问题吧！

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「AC 自动机」 以巩固所学知识。