使用Rabin-Karp算法替代KMP

Rabin-Karp算法 Rabin-Karp算法是利用滑动窗口的方式来计算哈希值，并通过该哈希值直接进行比较来判断字符串是否匹配，也就是消减了字符串比较的过程来实现 O(n) 的时间复杂度。废话不多说了，直接上干货。首先，我问你一个很基础的问题，给你输入一个字符串形式的正整数，如何把它转化成数字的形式？很简单，下面这段代码就可以做到：string s = "8264"; int number = 0; for (int i = 0; i < s.size(); i++) { // 将字符转化成数字 number = 10 * number + (s[i] - '0'); print(number); } // 打印输出： // 8 // 82 // 826 // 8264 可以看到这个算法的核心思路就是不断向最低位（个位）添加数字，同时把前面的数字整体左移一位（乘以 10）。为什么是乘以 10？因为我们默认探讨的是十进制数。这和我们操作二进制数的时候是一个道理，左移一位就是把二进制数乘以 2，右移一位就是除以 2。上面这个场景是不断给数字添加最低位，那如果我想删除数字的最高位，怎么做呢？比如说我想把 8264 变成 264，应该如何运算？其实也很简单，让 8264 减去 8000 就得到 264 了。这个 8000 是怎么来的？是 8 x 10^3 算出来的。8 是最高位的数字，10 是因为我们这里是十进制数，3 是因为 8264 去掉最高位后还剩三位数。上述内容主要探讨了如何在数字的最低位添加数字以及如何删除数字的最高位，用R表示数字的进制数，用L表示数字的位数，就可以总结出如下公式：/* 在最低位添加一个数字 */ int number = 8264; // number 的进制 int R = 10; // 想在 number 的最低位添加的数字 int appendVal = 3; // 运算，在最低位添加一位 number = R * number + appendVal; // 此时 number = 82643 /* 在最高位删除一个数字 */ int number = 8264; // number 的进制 int R = 10; // number 最高位的数字 int removeVal = 8; // 此时 number 的位数 int L = 4; // 运算，删除最高位数字 number = number - removeVal * R^(L-1); // 此时 number = 264 如果你能理解这两个公式，那么 Rabin-Karp 算法就没有任何难度，算法就是这样，再高大上的技巧，都是在最简单最基本的原理之上构建的。不过在讲 Rabin-Karp 算法之前，我们先来看一道简单的力扣题目。高效寻找重复子序列看下力扣第 187 题「重复的 DNA 序列」，我简单描述下题目： DNA 序列由四种碱基A, G, C, T组成，现在给你输入一个只包含A, G, C, T四种字符的字符串s代表一个 DNA 序列，请你在s中找出所有重复出现的长度为 10 的子字符串。比如下面的测试用例：输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出：["AAAAACCCCC","CCCCCAAAAA"] 解释：子串 "AAAAACCCCC" 和 "CCCCCAAAAA" 都重复出现了两次。输入：s = "AAAAAAAAAAAAA" 输出：["AAAAAAAAAA"] 函数签名如下：vector<string> findRepeatedDnaSequences(string s); 这道题的拍脑袋解法比较简单粗暴，我直接穷举所有长度为 10 的子串，然后借助哈希集合寻找那些重复的子串就行了，代码如下：// 暴力解法 vector<string> findRepeatedDnaSequences(string s) { int n = s.size(); // 记录出现过的子串 unordered_set<string> seen; // 记录那些重复出现多次的子串 // 注意要用哈希集合，防止记录重复的结果 unordered_set<string> res; for (int i = 0; i + 10 <= n; i++) { auto subStr = s.substr(i, 10); if (seen.count(subStr)){ // 之前出现过，找到一个重复的 res.insert(subStr); } else { // 之前没出现过，加入集合 seen.insert(subStr); } } return {res.begin(),res.en…