01先把问题说具体
同一个字符串要比较许多子串,逐字符比较很贵。能否先计算一组可快速提取的数字摘要?
02一步步得到方法
把字符当作进制中的数字
先把 a..z 映射为 1..26,选基数 B 与模数 M。前缀递推 H[i+1]=(H[i]·B+value(s[i])) mod M,类似把数字接到已有数值末尾。
长度 L 的子串 [l,r) 指纹为 H[r]−H[l]·B^L,再取模。减掉的项恰好是前 l 个字符在更长前缀中占据的高位部分,所以剩下子串不依赖原位置。
相等指纹只是候选相等
不同字符串可能映射到同一余数,这叫碰撞;M 个余数不可能唯一编码无限多字符串。双模或随机基数可降低风险,但仍不是数学上的绝对相等证明。
要求确定正确时,指纹命中后再逐字符验证,或选择 KMP、后缀结构等确定性方法。比较不同长度子串还应比较长度,避免让不同问题对象混用摘要。
哈希值是便宜的指纹而非唯一身份
把字符串映射成模数范围内的整数,便于快速比较候选。但字符串可能无限多、余数只有有限个,碰撞在数学上不可避免,所以哈希相等只能说明需要进一步确认。
前缀哈希让子串查询不再重新扫描整段;公式还要减去前缀对当前位置的幂次贡献。若做二分最长公共前缀,哈希只是加速每次相等判定,正确性仍需明确碰撞处理策略。
03把一个小例子完全算清楚
s='ababc',B=31,为手算取 M=101。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 前缀 a、ab | H[1]=1,H[2]=33 | 1×31+2=33 |
| 前缀 aba、abab | H[3]=14,H[4]=32 | 每步取模 101 |
| 子串 [2,4) | (32−33×31²) mod 101=33 | 与 [0,2) 的 ab 一致 |
窄屏可左右滑动表格,阅读完整计算与理由。
前缀减法消除了位置影响,却没有消除哈希碰撞。
04为什么这个方法成立
- 展开前缀多项式可分成前 l 项乘 B^(r−l) 与后面子串两部分。
- 两者相减恰好保留子串对应多项式。
- 取模保持加减乘关系,因此公式正确;指纹相同反推文本相同则不成立。
05把推导翻译成代码
Python · 可独立运行的教学实现
class StringHash:
def __init__(self, text, base=31, mod=1000000007):
assert all("a" <= c <= "z" for c in text)
self.mod, self.h, self.p = mod, [0], [1]
for c in text:
self.h.append((self.h[-1]*base+ord(c)-ord("a")+1)%mod)
self.p.append(self.p[-1]*base%mod)
def slice_hash(self,left,right):
assert 0 <= left <= right < len(self.h)
return (self.h[right]-self.h[left]*self.p[right-left])%self.mod逐个理解关键决定
self.p[right-left]- 指数是子串长度,不是右端下标。
%self.mod- 规范化相减后的余数;不同语言对负余数的规则要另外处理。
06时间、空间与实现范围
预处理 O(n) 时间与空间,单次指纹提取 O(1)(固定宽度算术模型)。
若命中后比较原文,单次确定性比较仍最坏 O(L);大量碰撞会拖慢基于指纹的筛选。
07改变条件,检查哪里会出错
哈希相同就直接宣称字符串相同
对于严格正确任务必须验证或选确定性结构。
把固定模数当作绝不碰撞
双哈希或随机参数可降低某些风险,但精确任务仍应设计验证或使用无碰撞保证的方法。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
空子串指纹是多少?
需要一点提示
H[l]−H[l]·B⁰。
查看解析与答案
0,长度为 0。
M=1 会发生什么?
需要一点提示
所有数模 1。
查看解析与答案
所有指纹都为 0,完全失去筛选能力,展示模数选择的重要性。
比较不同位置相同子串,为什么要乘 B 的幂?
需要一点提示
前缀高位权重发生了位移。
查看解析与答案
H[l] 在 H[r] 中向高位移动了 r−l 位,不乘就无法正确抵消。