### Rabin-Karp 算法简介 Rabin-Karp 是一种基于哈希函数的字符串匹配算法，它通过减少不必要的字符比较来提高效率。其核心思想是利用滚动哈希技术，在模式串和文本串之间快速找到可能的匹配位置[^1]。 此算法的时间复杂度通常为 \(O(n+m)\)，其中 \(n\) 表示文本长度，\(m\) 表示模式串长度。然而，在最坏情况下（例如当所有子串都具有相同的哈希值时），时间复杂度可能会退化到 \(O(n \cdot m)\)[^2]。 以下是 Rabin-Karp 算法的一个标准 Python 实现： ```python def rabin_karp(text, pattern, prime=101, base=256): n = len(text) m = len(pattern) if m > n or m == 0: return [] result = [] pattern_hash = 0 text_hash = 0 h = pow(base, m - 1, prime) # Precompute the highest power of 'base' # Compute hash value for pattern and first window of text for i in range(m): pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime text_hash = (base * text_hash + ord(text[i])) % prime # Slide the pattern over text one by one for i in range(n - m + 1): # Check whether current window matches with pattern using hash values if pattern_hash == text_hash: match = True for j in range(m): if text[i + j] != pattern[j]: match = False break if match: result.append(i) # Calculate hash value for next window of text: Remove leading digit, # add trailing digit if i < n - m: text_hash = (text_hash - ord(text[i]) * h) % prime text_hash = (text_hash * base + ord(text[i + m])) % prime if text_hash < 0: text_hash += prime return result ``` 上述代码实现了 Rabin-Karp 的基本逻辑，包括预处理阶段和滑动窗口阶段。为了防止整数溢出并加速计算，这里采用了模运算的方式生成哈希值[^4]。 ### 关于实现细节 - **参数说明**: `prime` 和 `base` 分别表示用于取模的大素数以及字符集大小，默认设置为常见的数值组合。 - **边界条件**: 如果模式串为空或者大于文本串，则直接返回空列表作为结果。 - **性能优化**: 使用预先计算好的幂次项 (`h`) 来简化每次更新操作中的乘方部分，从而提升整体运行速度。 值得注意的是，尽管 Rabin-Karp 提供了一种高效的解决方案，但在实际应用中仍需注意选择合适的散列函数以降低冲突概率。