上一页看到朴素匹配逐格挪动、每次都整段比对。模式串稍长，主串又大，这种「回头重来」的重复劳动会迅速堆出天文数字级的比较次数。

上一页看到朴素匹配每轮都逐字比较，太慢。生活中验钞不用逐张摸水印——先看编号对不对，编号不同直接淘汰。字符串也能这样：给每个子串算一个短"指纹"，先比指纹。

上一页说要给每个窗口算一个指纹。指纹从哪来？其实不用发明新东西——字符本来就是数字，那一段串就可以直接当成一个整数来读。

上一页我们把字符串当成大数，可这个数可能有上千位，没法直接比较。电话号码太长记不住，我们只记尾号四位——尾号相同再去核对全号，一下就把范围缩小了。

上一页我们用取模把串压成了指纹，但有个新麻烦：计算机的整数宽度是有限的，比如 64 位。m 位 Q 进制数动辄上百位，直接乘一次就『爆表』，指纹反而算不出来。

看边滚动边取模的写法：中间值始终小于 m²，乘法不溢出。

每步先乘 B 加新位再取模，值不超过 m²；减旧位用预取模的 B^(k-1)，全程不出现长度级大数。

前面我们把长数字「边算边取模」，指纹变得又小又快。但省事是有代价的：好几个不同的数除以同一个 M，余数可能完全相同——指纹一样，串未必一样。

从左到右看：每个窗口先比指纹，只有相等才进逐字核对，否则立即滑到下一个窗口。

指纹相同就等于匹配吗？两种判定方式的误判风险和代价差异，正是容易混淆的地方。

前面算好了一个窗口的指纹，但逐个重算整窗就又回到朴素匹配了。好在相邻窗口只差两个字符：走一格，最左边出去一个，右边进来一个。其实指纹不必重算，只需局部修补。

窗口右移一格，指纹不必重算——用旧指纹增量更新。

完整主循环：预计算首窗指纹，滑动时 O(1) 更新，命中再逐字验证。

循环前 O(m) 算好两个指纹；主循环每步先比对指纹，相等才做 O(m) 逐字验证；否则用更新公式 O(1) 滑到下一窗。

Karp-Rabin 中两个窗口的指纹相等，能得出什么结论？

• ✓指纹相等只是候选，逐字核对才算数
• ✓取模压住溢出，代价是引入碰撞风险
• ✓滑动窗口只需 O(1) 更新指纹
• ✓四环节闭环：压缩→溢出→冲突→更新

先自己想几分钟，再对照参考答案——三问都有回旋余地，不求唯一解。