Rabin-Karp字符串匹配算法详解（Python语言RK算法实现从零开始）

为什么选择RK算法？

• 适用于多模式匹配（可同时查找多个模式串）
• 平均时间复杂度为 O(n + m)，其中 n 是文本长度，m 是模式长度
• 实现相对简单，适合初学者理解哈希在算法中的应用

Python实现RK算法步骤

我们将按照以下步骤编写代码：

1. 定义一个哈希函数（通常使用滚动哈希）
2. 计算模式串的哈希值
3. 滑动窗口遍历文本串，计算每个子串的哈希值
4. 若哈希值匹配，则逐字符验证
5. 返回所有匹配位置

完整代码实现

def rabin_karp_search(text, pattern):    """    使用RK算法在text中查找pattern的所有出现位置    返回匹配起始索引的列表    """    if not pattern or not text:        return []        n = len(text)      # 文本长度    m = len(pattern)   # 模式长度        # 哈希参数    d = 256            # 字符集大小（ASCII）    q = 101            # 一个质数，用于取模防止哈希值过大        # 计算 d^(m-1) % q，用于滚动哈希    h = pow(d, m - 1, q)        # 初始化模式串和文本首窗口的哈希值    p_hash = 0  # pattern hash    t_hash = 0  # text window hash        # 计算初始哈希值    for i in range(m):        p_hash = (d * p_hash + ord(pattern[i])) % q        t_hash = (d * t_hash + ord(text[i])) % q        matches = []        # 滑动窗口遍历文本    for i in range(n - m + 1):        # 如果哈希值匹配，再逐字符验证        if p_hash == t_hash:            if text[i:i + m] == pattern:                matches.append(i)                # 计算下一个窗口的哈希值（如果不是最后一个窗口）        if i < n - m:            t_hash = (d * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % q            # 确保哈希值非负            if t_hash < 0:                t_hash += q        return matches# 测试示例if __name__ == "__main__":    text = "ABABDABACDABABCABCABCABC"    pattern = "ABC"    result = rabin_karp_search(text, pattern)    print(f"模式 '{pattern}' 在文本中出现的位置: {result}")

代码解析

d = 256 表示我们假设使用ASCII字符集（共256个字符）。q = 101 是一个质数，用于取模运算以避免整数溢出，并减少哈希冲突。

关键在于滚动哈希：当我们从窗口 [i, i+m-1] 移动到 [i+1, i+m] 时，不需要重新计算整个子串的哈希值，而是通过数学公式快速更新：

新哈希值 = (d × (旧哈希值 - 第一个字符 × d^(m-1)) + 新字符) mod q

运行结果示例

运行上述代码，输出为：

模式 'ABC' 在文本中出现的位置: [13, 16, 19]

总结

通过本教程，你已经学会了如何用Python语言实现RK算法进行高效的字符串匹配。RK算法虽然在最坏情况下时间复杂度为 O(nm)，但在实际应用中（尤其是随机文本）表现优异。掌握这一Rabin-Karp算法教程中的核心思想，将为你学习更高级的字符串算法（如KMP、Boyer-Moore）打下坚实基础。

希望这篇关于RK算法的入门指南对你有所帮助！动手试试修改代码，测试不同文本和模式，加深理解吧！