Rolling Hash / Rabin–Karp

字符串匹配、哈希与回文 · HTML

数学 / 逻辑形态

H[i+1]=(H[i]base+code(s[i])) mod M；hash(l,r)=H[r]-H[l]base^(r-l) mod M。

识别信号

• 大量子串相等比较
• 固定长度窗口查找
• 二分长度检测重复
• 确定性逐字符比较太贵
• 可接受碰撞验证或双哈希

容易误判的相似信号

核心不变量

prefix hash 表示从左到右的多项式；乘幂对齐后，相同子串产生相同指纹。

状态、转移与处理顺序

Python 骨架

class RollingHash:
    def __init__(self, s, base=911382323, mod=1_000_000_007):
        self.base, self.mod = base, mod
        self.h = [0] * (len(s)+1)
        self.p = [1] * (len(s)+1)
        for i, ch in enumerate(s):
            self.h[i+1] = (self.h[i]*base + ord(ch)+1) % mod
            self.p[i+1] = self.p[i]*base % mod
    def get(self, left, right):
        return (self.h[right] - self.h[left]*self.p[right-left]) % self.mod

def probably_equal_substrings(s, a, b, length):
    rh = RollingHash(s)
    return rh.get(a,a+length) == rh.get(b,b+length)

正确性思路

1. 前缀递推等价于字符系数的多项式。
2. 减去左前缀乘相应幂后只保留 [l,r) 的项。
3. 相同字符串的系数序列相同，因此哈希必相同。
4. 逆命题是概率性的；二次参数或原串验证控制碰撞。

复杂度

边界条件

• 空子串哈希应一致
• 模减法要归一化
• base 与 mod 应互相独立且合理
• 不同字符串实例需共享参数才能比较
• Unicode code point 与规范化需统一

错误模式

选择与排除规则

• 大量子串比较：rolling hash。
• 单模式最坏线性且零碰撞：KMP。
• 通过哈希二分长度时先确认可行谓词单调。
• 商业关键结果优先双哈希加原串验证。

相关模板

原创微型例子

Recall prompts

• 为何左前缀要乘 base 的幂？
• 哈希相同能证明什么、不能证明什么？
• 哪些场景必须验证碰撞？

我的补充