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为什么这个方法成立
- 滚动公式代数上等于新窗口的多项式值。
- 指纹不同排除真实匹配,因为相同原文必得相同指纹。
- 指纹相同后再检查原文,消除所有碰撞误报。
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,程序结果仍正确吗?
需要一点提示
每个窗口都会命中指纹。
查看解析与答案
仍正确,因为最后逐字符验证,但退化为逐窗口比较。
模式比文本长时呢?
需要一点提示
没有合法完整窗口。
查看解析与答案
返回空列表。
搜索很多等长模式如何复用?
需要一点提示
相同窗口指纹只算一次。
查看解析与答案
建立指纹到候选模式列表的映射,每个窗口只验证对应桶中的模式,仍注意碰撞与输出规模。