专题进阶 · 字符串算法推荐总顺序 · 第 95 / 148 课

维护固定长度窗口指纹,并用原文验证把概率筛选变成确定正确的匹配。

先学会这些,再进入本课 字符串哈希
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 字符串算法

Rabin–KarpRabin–Karp

用滚动哈希筛选匹配位置,哈希命中后验证字符可保证正确性。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

维护固定长度窗口指纹,并用原文验证把概率筛选变成确定正确的匹配。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

在 text='ababa' 中找 pattern='aba',每次窗口右移一位,怎样只更新离开与进入的字符?

02一步步得到方法

窗口右移等价于删高位、乘基数、加低位

长度 m 的窗口多项式为 x₀B^(m−1)+…+xₘ₋₁。移走首字符时减掉 x₀B^(m−1),再乘 B,让剩余字符权重左移,最后加新字符并取模。

提前计算 B^(m−1) mod M,就可每次常数次算术更新。模式指纹预先算好,窗口指纹不同时一定不是匹配,相同时才进一步检查字符。

正确性与效率分开承诺

逐字符验证使即使发生碰撞也不会误报,因此结果确定正确。不过若很多窗口指纹碰撞,或真实匹配很多且模式很长,每次验证 O(m),最坏总时间可能 O(nm)。

多个等长模式可以按指纹分桶,共享文本扫描;长度不同需不同窗口或其他结构。Rabin–Karp 的价值常在批量筛选,而不是保证单模式最坏优于 KMP。

滚动更新只负责筛出候选

窗口右移时去掉最左字符对应的高位贡献,剩余部分乘基数,再加新字符。这样每个窗口指纹可常数时间更新,而不是重新读取整段模式长度的字符。

为了得到确定正确的匹配位置,本课在哈希相等时再核对真实字符。候选很少时高效,但大量碰撞或大量真实匹配都可能让验证成本升高到 O(nm),不能把平均情形写成无条件最坏界。

03把一个小例子完全算清楚

字符取 Unicode 码点,B=31,M=101;窗口长度 3。

步骤计算与状态为什么这样做
窗口 aba指纹 99,与模式相同原文验证成功,记录 0
窗口 bab删首 a、乘 31、加 b,指纹 20无需比较完整原文
窗口 aba指纹回到 99验证成功,记录 2

窄屏可左右滑动表格,阅读完整计算与理由。

输出 [0,2],保留重叠窗口。

04为什么这个方法成立

  1. 滚动公式代数上等于新窗口的多项式值。
  2. 指纹不同排除真实匹配,因为相同原文必得相同指纹。
  3. 指纹相同后再检查原文,消除所有碰撞误报。

05把推导翻译成代码

Python · 可独立运行的教学实现

def rabin_karp(text,pattern,base=31,mod=1000000007):
    n,m = len(text),len(pattern)
    if m == 0:
        return list(range(n+1))
    if m > n:
        return []
    high = pow(base,m-1,mod)
    wanted = current = 0
    for i in range(m):
        wanted = (wanted*base+ord(pattern[i]))%mod
        current = (current*base+ord(text[i]))%mod
    result = []
    for left in range(n-m+1):
        if current == wanted and text[left:left+m] == pattern:
            result.append(left)
        if left+m < n:
            current = ((current-ord(text[left])*high)*base+ord(text[left+m]))%mod
    return result

逐个理解关键决定

text[left:left+m] == pattern
指纹只筛选,原文决定是否报告。
pow(base,m-1,mod)
首字符权重是 m−1 次幂,而不是 m 次幂。

06时间、空间与实现范围

预处理 O(m),滚动 O(n),另加每次候选验证成本;最坏 O(nm)。

工作状态为常数规模,Python 候选切片会临时创建 O(m) 字符对象,输出空间另计。

07改变条件,检查哪里会出错

删掉原文验证却仍说绝对正确

算法变为有碰撞风险的版本,应保留验证或明确错误概率模型。

忘记取模后的负值归一化

移除旧字符后可能暂为负数,跨语言实现需要统一余数范围。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

模数取 1,程序结果仍正确吗?

需要一点提示

每个窗口都会命中指纹。

查看解析与答案

仍正确,因为最后逐字符验证,但退化为逐窗口比较。

练习 2 · 边界与辨析

模式比文本长时呢?

需要一点提示

没有合法完整窗口。

查看解析与答案

返回空列表。

练习 3 · 变式与迁移

搜索很多等长模式如何复用?

需要一点提示

相同窗口指纹只算一次。

查看解析与答案

建立指纹到候选模式列表的映射,每个窗口只验证对应桶中的模式,仍注意碰撞与输出规模。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 字符串算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。