这篇是我学习 Rabin–Karp (Karp–Rabin) 演算法的一个纪录。

推荐读者要先有滑动窗口、hash collision(杂凑冲突)等演算法观念再来阅读。

Rabin–Karp（或 Karp–Rabin）演算法介绍

这个演算法的名字其实就是由发明者的名字 Michael O. Rabin 和 Richard M. Karp 来命名，所以标题的两种演算法名称都正确。

主要概念是透过 Rolling Hash(中文翻译叫旋转杂凑) 的杂凑函式，先计算两个比对字串的 hash 值后，再比对两个 hash 值是否相等，相等就有可能两个字串一样，不一样可以透过滑动窗口的演算法，窗口内的字串中，移除最左字元，加入最右字元，更新 hash 值，然后再和要搜寻字串的 hash 值做比对，因为比对 hash 值的过程只是比较数字，可以不用将两个字串都从头遍历，更新 hash 值也是不用，因此可以加速字串的搜寻。

hash 值求值举例说明

我们用 LeetCode 2156. Find Substring With Given Hash Value 题目提到的杂凑函式来举例：

  • s 代表的是一个字串，然后 val(s[i]) 代表一个字元经转换后的数值，这题是这样转换的，a 为 1、b 为 2、c 为 3...y 为 25、z 为 26。
  • p 代表的是基数(base)。
  • m 代表的是模数（modulo），通常选大质数，防止 hash collision，但计算比较吃力，取模是避免前面的乘积太大。

题目给的范例 1 中，s = \'ee\'、p = 7、m = 20，故hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0，0 就是这个段落要求的 hash 值。

在求得 hash 值后会和另外一个 hash 值做比较，而这另外一个 hash 值也是从一个字串计算而来，所以若两个值相同，在没有发生 hash collision 的情况下，两个字串就会相等。

由于可能会存在 hash collision 的可能，因此在 hash 值相等时，我们需要再额外判断其是否真正相等，这个可能性可以透过前面提到的 m 模数降低机率。

所以举个例子，s = "leetcode"，"ee" 字串我们已经知道 hash 值为 0，假设要在字串内找到 "od"，(15 * 1 + 4 * 7) mod 20 = 43 mod 20 = 3，两个 hash 值不相同，所以要继续搜寻其他子字串。

更新怎么做？

这里我承认偷懒了XD，直接取用 ChatGPT 的回答：

时间复杂度分析

透过以上 hash 值的求值过程，假设有一个长度为 n 的主要字串，还有一个长度为 m 的子字串，我们可以知道：

初始 hash 值计算是 O(m)，更新只需要 O(1)，然后遍历主要字串，会搜寻 n − m + 1 个子字串，为 O(n)，所以平均情况下是 O(n + m)。

最坏情况是常发生杂凑碰撞，时间复杂度退回 O(n * m)，故需要设计良好的杂凑函数。

适合可以同时搜寻多个字串、大量字串搜寻的情况。

参考资源

Rabin Karp - Shortest Palindrome - Leetcode 214

LeetCode 练习题

214. Shortest Palindrome

2156. Find Substring With Given Hash Value