为何Rabin-Karp字符串匹配算法实际效率低于暴力匹配算法？

你的测试结果其实很常见，核心原因在于Python解释型算术操作的开销和暴力算法的底层C级优化，再加上你的Rabin-Karp实现存在几个可优化的低效点：

1. 暴力算法的底层天然优势 #

你写的暴力匹配里，stringInp[i - len(matchInp): i] == matchInp 看似是Python代码，但字符串切片和相等比较都是Python内置的C语言实现，执行速度远快于你用Python循环做的哈希计算、模运算这些解释型操作。哪怕暴力算法最坏时间复杂度是O(n*m)，但实际测试中（尤其是匹配位置靠前的场景），底层优化带来的速度提升完全盖过了理论复杂度的劣势。

2. 你的Rabin-Karp实现的几个低效点 #

（1）未优化的幂运算 #

h = d ** (len(containStr) - 1) 这行如果模式串较长，会直接计算一个超大整数，后续运算开销极大。Python内置的pow(base, exp, mod)函数支持在计算过程中直接取模，不仅能避免大整数运算，还因为是C优化实现，速度快很多。

（2）冗余的模运算 #

更新currHash时你做了两次% p：

currHash = (currHash - ord(inpStr[i - len(containStr)]) * h) % p
currHash = (currHash * d + ord(inpStr[i])) % p

其实可以合并成一次，减少模运算的次数：

currHash = ((currHash - ord(inpStr[i - len(containStr)]) * h) * d + ord(inpStr[i])) % p

（3）缺失哈希冲突验证 #

当前实现只要哈希相等就直接返回True，但哈希存在冲突概率（哪怕极低），正确的Rabin-Karp应该在哈希匹配后再做一次字符串精确匹配。不过这一点不是你当前速度慢的核心原因，但会导致算法正确性有隐患。

（4）循环中的重复属性访问 #

每次循环里重复调用len(containStr)，虽然Python的len是O(1)操作，但提前把pattern_len = len(containStr)存为变量，循环里直接使用，能稍微减少一点不必要的属性访问开销。

优化后的Rabin-Karp实现 #

试试这个版本，能明显拉近和暴力算法的速度差距：

def rabinKarp(self, inpStr, containStr) -> bool:
    pattern_len = len(containStr)
    input_len = len(inpStr)
    if pattern_len > input_len:
        return False

    d, p = 52, 2**16 + 7
    searchHash = 0
    currHash = 0

    # 预计算h = d^(pattern_len-1) mod p，用内置pow优化
    h = pow(d, pattern_len - 1, p)

    # 一次性计算初始哈希，减少循环次数
    for i in range(pattern_len):
        searchHash = (searchHash * d + ord(containStr[i])) % p
        currHash = (currHash * d + ord(inpStr[i])) % p

    for i in range(pattern_len, input_len):
        if currHash == searchHash:
            # 哈希匹配后做精确验证，避免冲突
            if inpStr[i-pattern_len:i] == containStr:
                return True
        # 合并哈希更新与模运算
        currHash = ((currHash - ord(inpStr[i - pattern_len]) * h) * d + ord(inpStr[i])) % p

    # 检查最后一个窗口
    if currHash == searchHash and inpStr[-pattern_len:] == containStr:
        return True
    return False

额外说明 #

Rabin-Karp的优势通常在多模式匹配或者极长模式串场景下才能体现。对于单模式匹配，尤其是在Python这种解释型语言里，暴力匹配因为底层C优化，很多时候都会比纯Python实现的Rabin-Karp快。如果要真正发挥Rabin-Karp的性能，可能需要用C扩展或借助numpy这类库加速哈希计算。

内容的提问来源于stack exchange，提问作者Alex