AI summary
type
status
date
slug
summary
category
tags
icon
password
今天就来讲一讲经典的 Rabin-Karp 字符串匹配算法。
本文会由浅入深地讲明白这个算法的核心思路，先从最简单的字符串转数字讲起，然后研究一道力扣题目，到最后你就会发现 Rabin-Karp 算法使用的就是滑动窗口技巧，直接套前文讲的 滑动窗口算法核心代码模板 就出来了，根本不用死记硬背。
废话不多说了，直接上干货。
首先，我问你一个很基础的问题，给你输入一个字符串形式的正整数，如何把它转化成数字的形式？很简单，下面这段代码就可以做到：
上面这个场景是不断给数字添加最低位，那如果我想删除数字的最高位，怎么做呢？比如说我想把 8264 变成 264，应该如何运算？其实也很简单，让 8264 减去 8000 就得到 264 了。
这个 8000 是怎么来的？是 8 x 10^3 算出来的。8 是最高位的数字，10 是因为我们这里是十进制数，3 是因为 8264 去掉最高位后还剩三位数。
如果你能理解这两个公式，那么 Rabin-Karp 算法就没有任何难度，算法就是这样，再高大上的技巧，都是在最简单最基本的原理之上构建的。不过在讲 Rabin-Karp 算法之前，我们先来看一道简单的力扣题目。

高效寻找重复子序列

187. 重复的DNA序列

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。
  • 例如，"ACGAATTCCG" 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
这道题的拍脑袋解法比较简单粗暴，我直接穷举所有长度为 10 的子串，然后借助哈希集合寻找那些重复的子串就行了。这个算法肯定是没问题的，只是时间复杂度略高，假设 s 的长度为 N，目标子串的长度为 L，for 循环遍历 O(N) 个字符，对每个字符都要截取长度为 L 的子串，所以时间复杂度为
在 Python 中，字符串切片（slicing）的时间复杂度是 O(k)，其中 k 是切片的长度。
因为 Python 字符串是不可变的，所以切片操作会创建一个新的字符串，并将切片部分的字符复制到新字符串中。
注意我们这个匹配过程实际上就是维护了一个长度为 L = 10 的定长窗口在从左向右滑动，是否可以借鉴前文滑动窗口中的做法，只维护 left, right 指针来划定子字符串区间？
其实可以的，但是依然需要将窗口中的字符转化成字符串然后去 seen 集合判断是否存在重复，时间复杂度并没有降低。
所以优化的关键在于，我们能不能不要真的把子字符串生成出来，而是用一些其他形式的唯一标识来表示滑动窗口中的子字符串，并且还能在窗口滑动的过程中快速更新？
有办法的，回想一下本文开头我们讨论的那两个公式，现在你应该明白的用意了。
你把 AGCT 四种字符等价为 0123 四个数字，那么长度为 L = 10 的一个碱基序列其实就可以等价为一个十位数，这个数字可以唯一标识一个子串。而且窗口移动的过程，其实就是给这个数字的最低位添加数字，并删除最高位数字的过程，回顾之前的讲解，添加和删除数字的运算就是两个公式，可以在 O(1) 的时间完成。
然后，我们不要在哈希集合中直接存储子串了，而是存储子串对应的十位数。因为一个十位数可以唯一标识一个子串，所以也可以起到识别重复的作用。
其实你想下，你把一个字符串对象转化成了一个数字，这是什么？这就是你设计的一个哈希算法，生成的数字就可以认为是字符串的哈希值。在滑动窗口中快速计算窗口中元素的哈希值，叫做滑动哈希技巧。
进一步，我们用一个长度为 10 的十进制数来标识一个长度为 10 的碱基字符序列，这个数字可能达到 10^10，int 存不下，这需要 long 类型存储。但你注意这个十进制数中的每一位数字只会局限于 0,1,2,3，是不是有些浪费？
换句话说，我们需要存储的其实只是一个长度为 10 的四进制数（共包含 4^10 个数字），却用了长度为 10 的十进制数（可以包含 10^10 个数字）来保存，显然是有些浪费的。
因为 4^10 = 2^20 = 1048576 < 2^31-1，int 类型就够存了。
结合数字最高/最低位的处理技巧和滑动窗口代码框架，我们就可以轻松地写出最终的解法代码：
滑动窗口算法本身的时间复杂度是 O(N)，再看看窗口滑动的过程中的操作耗时，给 res 添加子串的过程用到了 substring 方法需要 O(L) 的复杂度，但一般情况下 substring 方法不会调用很多次，只有极端情况（比如字符串全都是相同的字符）下才会每次滑动窗口时都调用 substring 方法。
所以我们可以说这个算法一般情况下的平均时间复杂度是 O(N)，极端情况下的时间复杂度会退化成 O(NL)。

Rabin-Karp 算法

28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
有了上面由浅入深的铺垫，你理解 Rabin-Karp 算法就非常容易了，因为上面这道题目的本质就是一个字符串匹配的问题。
字符串匹配算法大家都很熟悉，让你在文本串 txt 中搜索模式串 pat 的起始索引。
相对上一道题的解法，只需要将进制数 R 改为了 256（ASCII 码的个数），同时计算了模式串 pat 的哈希值 patHash 用来和窗口中字符串的哈希值 windowHash 做对比，以便判断是否找到了模式串，其他的代码部分完全相同。
不过呢，这段代码实际运行的时候会有一个严重的问题，那就是整型溢出。
现在输入为 ASCII 码字符串，我们不得不把字符串抽象成 256 进制的数字，即算法中 R = 256。而相同位数下，256 进制包含的数字数量显然是远大于十进制包含的数字数量的。比如 L = 10 时，256^10 = 1.2 x 10^24 < 10 ^25，所以你需要一个 25 位的十进制数才能表示一个 10 位的 256 进制数。
可想而知，如果你真的把字符串对应的 256 进制数字的十进制表示作为该字符串的哈希值，那恐怕 L 稍微大一点，像 RL, windowHash, patHash 这些变量就超级大了，long 类型都远远装不下。
所以解决办法是什么呢？如何把一个很大的数字映射到一个较小的范围内呢？答案是求模（余数）。这个技巧也是我们在 哈希表原理及实现 中讲过的。
无论一个数字多大，你让它除以 Q，余数一定会落在 [0, Q-1] 的范围内。所以我们可以设置一个 Q，用求模的方式让 windowHash 和 patHash 保持在 [0, Q-1] 之间，就可以有效避免整型溢出。
好，整型溢出的问题倒是解决了，但是求模之后的哈希值不能和原始字符串一一对应了，可能出现一对多的情况，即哈希冲突。
比方说 10 % 7 等于 3，而 17 % 7 也等于 3，所以如果你得到余数 3，你能确定原始数字就一定是 10 么？不能。
类似的，如果你发现 windowHash == patHash，你也不敢完全肯定窗口中的字符串一定就和模式串 pat 匹配，有可能它俩不匹配，但恰好求模算出来的哈希值一样，这就产生了是「哈希冲突」。
对于 Rabin-Karp 算法来说，当发现 windowHash == patHash 时，使用暴力匹配算法检查一下窗口中的字符串和 pat 是否相同就可以避免哈希冲突了。因为哈希冲突出现的概率比较小，所以偶尔用一下暴力匹配算法是不影响总体的时间复杂度的。
有之前那么多铺垫，算法逻辑应该没啥可说的，就说一下模运算的两个运算法则吧：
稍微想一想就能理解这两个运算法则，在代码中但凡涉及到乘法和加法，都可能产生很大的结果，所以一有机会就可以运用上述法则对结果进行求模，以避免造成溢出。
Rabin-Karp 算法的时间复杂度是 O(N+L)，N 为文本串 txt 的长度，L 为模式串 pat 的长度。当然，每次出现哈希冲突时会使用 O(L) 的时间进行暴力匹配，但考虑到只要 Q 设置的合理，哈希冲突的出现概率会很小，所以可以忽略不计。
最后说一下这个大素数 Q 的选择。
为什么要这个 Q 尽可能大呢？主要是为了降低哈希冲突的概率。
因为代码中你把这个 Q 作为除数，余数（哈希值）一定落在 [0, Q-1] 之间，所以 Q 越大，哈希值的空间就越大，就越不容易出现哈希冲突，整个算法的效率就会高一些。
为什么这个 Q 要是素数呢？依然是为了降低哈希冲突的概率。
举个极端一点的例子，你令 Q = 100，那么无论一个数 X 再大，X % Q 的结果必然是 X 的最后两位。换句话说 X 前面的那些位你根本没利用，可想而知你这个哈希算法存在某些规律性，不够随机，进而更容易导致哈希冲突，降低算法的效率。
而如果你把 Q 设置为一个素数，可以更充分利用被除数 X 的每一位，得到的结果更随机，哈希冲突的概率更小。这个结论是能够在数学上证明的，有兴趣的读者可以自行搜索学习，我这里就不展开了。