Rabin–Karp 算法

把窗口想成一个 $B$ 进制数：向右移动时，先减去离开字符的最高位贡献，再整体左移一位，最后补入新字符。模数让这个数保持在有限范围内，也让不同字符串可能落到同一个余数。因此指纹提供的是廉价排除条件，相等本身不证明字符串相等。

图中先做滚动筛选，再走字符核验分支；只有后一步才能把候选变成确定匹配。

用数字字符自身编码，取 $B=10,p=13$，在文本 1234 中搜索模式 23。首窗 12 的指纹为 $12$，模式指纹为 $23mod13=10$，二者不同。窗口右移得到

核验两个字符后确认位置 $1$ 匹配；再滚动得到 $h_2=((10-2\cdot 10)\cdot 10+4)mod13=8$，对应 34。这里必须把负余数规范到 $0,\dots ,p-1$。此外，10 与 23 都模13余10，是不同窗口仍会碰撞的具体例子。

文本 abracadabra 中搜索 abra 时，首窗和位置7的窗口都是真匹配。若任务只找首个位置，首窗确认后即可停止；若报告全部位置，就要继续扫描。这一区别会影响时间分析：在全由 a 组成的长文本中搜同样全由 a 组成的模式，每个窗口都真匹配，逐次完整核验会耗费 $\mathrm{\Theta }((n-m+1)m)$，随机哈希消除不了这项成本。

参数随机性也有明确前提。例如取素数 $p$，要求字符编码在 ${\mathbb{F}}_p$ 中也互异（可将至多 $p$ 种字符编码为 $0,\dots ,p-1$），固定一对不同的等长字符串后，再从非零域元素中均匀选择 $B$；两指纹之差是次数至多 $m-1$ 的非零多项式，在域中至多有 $m-1$ 个根，碰撞概率至多 $min(1,(m-1)/(p-1))$。仅让整数编码互异还不够：若两个字符编码模 $p$ 相同，长度一的不同字符串就会对所有基数碰撞。此处假定输入不依赖随机种子；固定弱参数不能用这条结论对抗刻意构造的碰撞。

在字长 RAM 中，若模乘可在常数成本内完成，预处理和滚动扫描耗时 $O(n+m)$。记触发核验的窗口数为 $k$，确定性上界是 $O(n+m+km)$。寻找首个匹配时至多完整核验一次真匹配；只有在随机参数保证假命中核验的期望总成本为 $O(n+m)$ 时，才能得到通常所说的期望线性时间。最坏情形仍可达到 $O(nm)$；任意精度整数则另有位运算成本。

字符串匹配理路字符串匹配String matching · Exact pattern matching在文本中定位模式串全部出现位置的问题。是任务，模同余理路模同余Congruence modulo n两整数之差被给定正整数整除时成立的等价关系。支撑滚动更新，随机化理路随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。提供碰撞概率分析。通用哈希理路通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。给出“对任意固定不同键，随机选函数后碰撞概率小”的族性质；滚动多项式指纹还要求窗口能在 $O(1)$ 时间删首添尾，不能把任意通用族直接换进公式。Rabin–Karp 因而适合同长多模式、二维窗口、重复块筛选和文档片段指纹；最后一种仍需把“快速发现候选相似块”与“抗篡改的密码学摘要”分开。

它仍是顺序扫描一次文本的候选过滤器。若文本固定、模式查询很多，FM-index理路FM-indexFM-index · Full-text minute-space index在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。会预处理 BWT 与 rank 结构，以压缩空间回答 count，并为定位另付采样成本。双模数只能降低工程碰撞概率，不等于这种静态全文索引，也不能替代对随机参数和核验策略的正式说明。