Rabin–Karp 算法

Rabin–Karp算法
术语名称	Rabin–Karp算法
英语名称	Rabin–Karp algorithm
别名	RK算法, Karp–Rabin算法, Karp–Rabin algorithm

Rabin–Karp 算法(Rabin–Karp algorithm, RK)是一种字符串匹配算法，核心是利用某种哈希函数对文本串进行可能匹配位置的预筛选。这通常要求哈希函数是一个滚动哈希，以便于寻找与模式串哈希匹配的位点。

原理

字符串匹配问题的暴力算法要在每个位置尝试从头开始匹配模式，也就是需要最多 [math]\displaystyle{ (n-m)m = O(mn) }[/math] 次将每一个位置开始的字符串和模式串依次逐字符匹配。

RK 算法尝试对这些位置进行基于哈希的初筛，通过哈希值是否匹配确认哪些位置需要实际进行模式的匹配。

伪代码

过程 RabinKarp匹配
别名 rabin_karp_match
参数 text : 字符串 // 主文本
参数 pattern : 字符串 // 模式串
参数 hash : 字符串到整数的函数 // 整体计算哈希值
参数 hash_update : 整数、字符、字符到整数的函数 // 滚动哈希给定出入字符更新哈希值
返回 : 整数 // 匹配位置

令 n ← |text|, m ← |pattern|

令 p_hash ← 0  // 模式串哈希
令 t_hash ← 0  // 文本窗口哈希

p_hash ← hash(pattern₀..ₘ₋₁)
t_hash ← hash(text₀..ₘ₋₁)

循环 i ← 0 到 n - m:
    如果 p_hash = t_hash 那么
        令 match ← true
        循环 j ← 0 到 m-1
            如果 textᵢ₊ⱼ ≠ patternⱼ 那么
                match ← false
                跳出循环
        继续循环 j
        如果 match 那么
            返回 i
    
    如果 i ≤ n - m 那么
        跳出循环 // 剩余长度不足

    t_hash ← hash_update(t_hash, textᵢ, textᵢ₊ₘ) // 滚动哈希。若复杂度允许，也可以是重新计算

继续循环 i

返回 空可选值 // 未找到匹配

时间复杂度

与哈希函数相关，受到计算哈希函数本身复杂度、更新复杂度以及文本中子串的碰撞频率影响。

比较阶段，如果这些都是常数次，且碰撞频率忽略不计，则平均复杂度为 [math]\displaystyle{ O(n) }[/math] ，平均为在每个字符处重新或滚动地计算一次哈希值。 最坏情况下，每个哈希值都发生冲突，此时会退化成暴力搜索，最坏复杂度达到 [math]\displaystyle{ O(mn) }[/math] 。

如果考虑预处理阶段，还需要加上哈希函数应用于模式串的时间复杂度。

空间复杂度

与 [math]\displaystyle{ n }[/math] 无关，是常数 [math]\displaystyle{ O(1) }[/math] 。

改进

多哈希函数过滤，实际使用类似 Bloom 过滤器。