Rabin-Karp 字符串匹配
字符串 · 滚动哈希
用一个「哈希」代替逐字符比
在文本 abcabcab 里找模式 cab。KMP 靠部分匹配表跳过冗余比较，Rabin-Karp 则换个思路：给每个长度 m 的窗口算一个哈希值（把这段字符压成一个数），拿它和模式的哈希比。哈希不等，这段绝不可能匹配，直接跳过；只有哈希相等时，才逐字符验证一次。
滚动哈希：O(1) 更新
把字符看成数字（a=1, b=2, c=3），用多项式哈希：hash = (…(s₀·B + s₁)·B + … + sₘ₋₁) mod M（这里 B=10, M=997）。模式 cab 的哈希是 3·100 + 1·10 + 2 = 312。关键在滚动：窗口右移一格时，不用重算整段——去掉最左字符的贡献、乘上 B、加上新进来的字符，一步 O(1) 就得到新窗口的哈希。于是整趟扫描只花 O(n + m)（平均）。
下面是 T=abcabcab、P=cab（哈希 312）。点「下一步」逐步看：浅蓝色是当前窗口，变量面板显示窗口哈希 vs 模式哈希。哈希不等就跳过（很快）；哈希相等（下标 2、5 处都是 312）就逐字符验证，通过则命中、整段标绿。右侧代码随每一步同步高亮。
T
a
b
c
a
b
c
a
b
P
c
a
b
先算模式哈希：hash("cab") = 312；从第 0 个窗口开始，每格只比一个哈希数
1function rabinKarp(text: string, pat: string): number[] {
2 const n = text.length, m = pat.length;
3 const B = 10, M = 997;
4 const val = (ch: string) => ch.charCodeAt(0) - 96;
5 let patHash = 0, winHash = 0, pow = 1;
6 for (let k = 0; k < m; k++) {
7 patHash = (patHash * B + val(pat[k])) % M; // 模式哈希
8 winHash = (winHash * B + val(text[k])) % M; // 首窗口哈希
9 if (k < m - 1) pow = (pow * B) % M;
10 }
11 const res: number[] = [];
12 for (let i = 0; i + m <= n; i++) {
13 if (winHash === patHash) { // 哈希命中
14 if (text.slice(i, i + m) === pat) { // 逐字符验证
15 res.push(i);
16 }
17 }
18 if (i + m < n) { // 滚动更新 O(1)
19 winHash = ((winHash - val(text[i]) * pow) * B + val(text[i + m])) % M;
20 winHash = ((winHash % M) + M) % M;
21 }
22 }
23 return res;
24}
文本 Tabcabcab
模式 Pcab
模式哈希312
窗口哈希123
已找到—
1 / 12
哈希会「撞车」，所以要验证
两段不同的字符可能算出同一个哈希（哈希冲突）——所以哈希相等只是「可能匹配」，必须逐字符验证才能确认，否则会误报。
用大素数模 + 随机基能把冲突概率压到极低；工程里也常用双哈希（两个独立哈希都相等才验证）。
本页用小模数
用大素数模 + 随机基能把冲突概率压到极低；工程里也常用双哈希（两个独立哈希都相等才验证）。
本页用小模数
997 是为了让哈希是好读的三位数；此例恰好没有冲突。 滚动哈希不止用于单模式匹配：它是多模式匹配、最长重复子串、文件/文本指纹去重的通用工具。与 KMP 对比——KMP 用「模式的结构」（部分匹配表）省比较，Rabin-Karp 用「哈希」把比较压成比一个数，两条不同的加速路。