Rabin-Karp 字符串匹配
Rabin-Karp 比较固定长度文本窗口的哈希指纹。窗口每右移一位，滚动哈希就在常数时间内更新它的指纹，因此多数窗口只需一次哈希比较就能排除；哈希相同的窗口还要逐字符验证，全部相等才接受。
哈希把字符串压缩成小整数，不同字符串可能得到同一值。精确性来自最终字符检查：哈希相等只允许进入验证，不证明匹配。本课使用十进制数字展示滚动算术，普通文本也可以把字符映射成数值后处理。
滚动更新指纹
设模式长度为 m、基数为 10、模数为 q。窗口 31428 可看成十进制数，算法只保存除以 q 的余数。
先计算最高位因子：high = 10^(m - 1) mod q。模式和第一个窗口逐位初始化：hash = (10 × hash + digit) mod q。
窗口右移一格，左侧退出数字为 out，右侧进入数字为 in，则：
next = (10 × (windowHash - out × high) + in) mod q
减去最高位贡献，乘 10 将余下数字左移，再加入新个位。只需旧指纹、退出数字和进入数字，不必重读其他 m - 1 个字符。
JavaScript 的 % 可能返回负余数，实现用 (raw % q + q) % q 规范化。负中间值本身不错误，它属于同一个模剩余类，但保存和比较时要使用一致表示。
Rabin-Karp 逐步演示
默认文本为 3142831415，模式为 31415，q = 13。
- 模式长 5，所以
high = 10^4 mod 13 = 3。 - 模式逐位计算出的指纹为 7，第一个窗口
31428的指纹也为 7。 - 哈希相同，进入逐字符验证。3、1、4 相同，偏移 3 处
2 != 1，因此是碰撞，不是匹配。 - 右移一格，退出 3、进入 3。原始计算为
10 × (7 - 3 × 3) + 3 = -17。规范化模 13 后为 9，对应窗口14283。 - 继续滚动并比较，哈希不同的窗口不做字符检查。
- 位移 5 时窗口为
31415，指纹再次为 7。五个字符全部相等，返回 5。
完整轨迹共有六次哈希检查、五次滚动、九次字符检查。前四次字符检查排除位移 0 的假候选，后五次确认位移 5 的匹配。
模数如何改变工作量
保持文本和模式不变，把 q 从 13 改成 101，答案不变，但首个假候选消失。
31428 与 31415 相差 13，所以模 13 都为 7。模 101 时分别为 17、4，第一个窗口在哈希比较时就被排除，只有真实匹配进入字符验证。
较大模数通常减少偶然相等的机会，但不能消除碰撞。实际实现可用更大模数、机器字哈希或两个独立哈希；若要求精确搜索，仍需最终相等检查，除非应用明确接受碰撞风险。
为什么结果正确
相同字符串在相同基数和模数下必有相同哈希，因此哈希不同的窗口可以安全排除。反过来，哈希相同不保证字符串相同，所以必须逐字符确认。
滚动递推与重新计算整个窗口得到同一多项式指纹：移除最高位项，将剩余项左移，加入新项，就是下一个窗口的多项式。中间取模不改变最终余数。
时间与空间复杂度
设文本长 n、模式长 m，表中的窗口扫描假设 m ≤ n。
| 工作 | 时间 | 辅助空间 |
|---|---|---|
| 初始化模式与首窗口 | O(m) | O(1) |
| 滚动所有窗口 | O(n - m + 1) | O(1) |
| 验证一个候选 | O(m) | O(1) |
| 碰撞稀少时的期望完整搜索 | O(n + m) | O(1) |
| 最坏 | O(nm) | O(1) |
滚动扫描本身是线性的。最坏成本来自大量哈希候选，每个都比较接近 m 个字符才失败。碰撞风暴预设有五个窗口通过哈希筛选，却没有一个是真匹配。弱哈希、对抗输入或不合适的模数都会削弱筛选作用；期望线性依赖相应的哈希和输入假设，不是固定小模数对任意输入的保证。
何时使用 Rabin-Karp
一次普通子串查询通常用语言内置搜索。多个相同长度模式可以共享一次滚动扫描：先存储模式哈希，只验证哈希命中的窗口。重复片段、抄袭候选检测也能采用滚动窗口，并处理碰撞；二维匹配可先沿行再沿列滚动。
单模式的 KMP 有确定的 O(n + m) 上界，不依赖碰撞频率。Rabin-Karp 的固定宽度扫描便于扩展到等长模式批量匹配，选择应由任务决定。
边界情况
- 模式长于文本，没有合法窗口，返回
-1。 - 空文本配非空模式，也返回
-1。 - 单个数字模式仍适用，
high = 1。 - 前导零安全，因为窗口宽度固定，
0012和12不会被当成相同长度比较。 - 必须检查最后一个合法位移
n - m。 - UI 要求非空模式；展示函数另有已说明的约定，空模式返回 0。
常见错误
- 哈希相等就返回。默认首窗口会产生假匹配。
- 每次重新读取 m 个字符计算窗口哈希，使滚动阶段也变成 O(nm)。
- 减去
out而非out × high，没有删除正确位权。 - 直接用可能为负的余数与标准指纹比较。先规范化，后续保存和比较才一致。
- 把教学用小模数直接用于实际负载，造成过多候选验证。
- 将每次哈希命中称为碰撞。验证前只是候选，字符串不同才算碰撞。