Rabin-Karp算法

Rabin-Karp算法是一种基于哈希的高效字符串匹配算法，由Richard M. Karp和Michael O. Rabin于1987年提出。该算法通过计算模式串和文本子串的哈希值来快速比较，从而减少不必要的逐字符匹配，适用于单模式或多模式字符串搜索场景。

算法原理[编辑 | 编辑源代码]

Rabin-Karp算法的核心思想是：

将模式串和文本中的每个可能匹配的子串转换为哈希值。
如果哈希值匹配，再进行逐字符验证（避免哈希冲突导致的误判）。
利用滚动哈希（Rolling Hash）技术，使子串哈希值的计算时间从O(m)优化至O(1)（m为模式串长度）。

哈希函数设计[编辑 | 编辑源代码]

常用哈希函数为多项式滚动哈希： $H (S) = (s_{0} \cdot d^{m - 1} + s_{1} \cdot d^{m - 2} + \dots + s_{m - 1}) mod q$ 其中：

$d$ 是字符集大小（如ASCII为256）
$q$ 是一个大素数（减少哈希冲突）
$m$ 是模式串长度

滚动哈希计算[编辑 | 编辑源代码]

当窗口向右滑动时，新哈希值可通过旧值递推： $H (S_{i + 1}) = (d \cdot (H (S_{i}) - s_{i} \cdot d^{m - 1}) + s_{i + m}) mod q$

算法步骤[编辑 | 编辑源代码]

1. 计算模式串的哈希值 $H_{pattern}$ 。 2. 计算文本前 $m$ 个字符的哈希值 $H_{window}$ 。 3. 从第1个字符开始滑动窗口：

  * 若  $H_{window} = H_{pattern}$ ，则逐字符验证。
  * 更新  $H_{window}$  为下一个窗口的哈希值。

4. 重复直至文本末尾。

代码示例[编辑 | 编辑源代码]

以下是Python实现：

def rabin_karp(text, pattern):
    d = 256  # 字符集大小
    q = 101  # 大素数
    m = len(pattern)
    n = len(text)
    h_pattern = 0
    h_window = 0
    h = pow(d, m-1, q)  # d^(m-1) mod q
    result = []

    # 计算模式串和初始窗口的哈希值
    for i in range(m):
        h_pattern = (d * h_pattern + ord(pattern[i])) % q
        h_window = (d * h_window + ord(text[i])) % q

    # 滑动窗口
    for i in range(n - m + 1):
        if h_window == h_pattern:
            # 哈希匹配时逐字符验证
            if text[i:i+m] == pattern:
                result.append(i)
        if i < n - m:
            # 滚动哈希计算下一个窗口
            h_window = (d * (h_window - ord(text[i]) * h) + ord(text[i+m])) % q
            h_window = h_window if h_window >= 0 else h_window + q
    return result

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABC"
print("匹配位置索引:", rabin_karp(text, pattern))

输出:

匹配位置索引: [10]

复杂度分析[编辑 | 编辑源代码]

时间复杂度：

 * 最坏情况： $O (n \cdot m)$ （每次哈希匹配都需逐字符验证）
 * 平均情况： $O (n + m)$ （良好哈希函数下冲突少）

空间复杂度： $O (1)$ （仅需存储哈希值和常数变量）

实际应用案例[编辑 | 编辑源代码]

1. 文档搜索：在文本编辑器中快速查找关键词。 2. 抄袭检测：比较文档中连续字符串的相似性。 3. 生物信息学：DNA序列模式匹配（如查找特定基因片段）。

与其他算法的比较[编辑 | 编辑源代码]

算法	预处理时间	匹配时间	适用场景
Rabin-Karp	$O (m)$	$O (n + m)$	多模式匹配、流数据
Knuth-Morris-Pratt (KMP)	$O (m)$	$O (n)$	单模式精确匹配
Boyer-Moore	$O (m + σ)$	$O (n / m)$ （最佳）	长模式串

优化技巧[编辑 | 编辑源代码]

双哈希：使用两个不同 $q$ 值减少冲突概率。
多模式匹配：并行计算多个模式串的哈希值（如AC自动机的补充）。

可视化示例[编辑 | 编辑源代码]

常见问题[编辑 | 编辑源代码]

Q: 为什么选择大素数 $q$ ？

 * A: 减少哈希冲突概率，使哈希分布更均匀。

Q: 如何处理哈希溢出？

 * A: 使用模运算限制值范围，或换用更大整数类型。