TwoPointers_4_Rabin_Karp

  1. Rabin-Karp理解流
  2. 187.重复的DNA序列
  3. 28.找出字符串中第一个匹配项的下标

Rabin-Karp理解流

1.Rabin-Karp是字符匹配算法的是一种字符串匹配算法, 该算法理解成本比KMP要低很多, 实现起来思路比较容易写出, 效率也很高; Rabin-Karp 算法采用的是滑动哈希的技巧, 然后辅助以特殊的哈希规则实现; 理解该算法的思路路径为如下过程, 每个过程都容易理解, 只要穿起来整体就是Rabin-Karp算法; 个人认为是真的简单而优雅
2.理解路径: 1.字符串删除第一位和增加后一位的实现方法 => 2.滑动窗口暴力实现字符串的复杂度问题分析 => 3.采用滑动哈希避免单个字符串截取 => 4.数字按照进制进行哈希的方法 => 5.字符哈希的方法及应对哈希冲突
3.代表性理解题目 187.重复的DNA序列

1.字符串删除最高位和添加到最低位实现方法

// 如果想对8264增加最低位3
int number = 8264;
int R = 10;
int appVal = 3;
// 运算逻辑: 实现在低位增加1位;
number = R * number + appVal;

// 如果想对8264删除最高位8
int number = 8264;
int R = 10;
int removeVal = 8;
int L = 4; // 此时number的总位数
// 运算逻辑: 实现在低位增加1位;
number = number - removeVal * pow(R, (L-1));

2.回归到字符串匹配问题, 我们有长度为L的模式串, 以及长度为N的字符串需要匹配, 暴力方法 O(NL), N这个是无法降低字符串的, 优化方向在于匹配串L上; 其实现结构如下

int L = 10;
unordered_set<string> seen;

string window = "";
int left = 0;
int right = 0;
while (right < s.size()) {
  window.push_back(s[right]);
  ++right;

  if (right - left == L) {
    // 把窗口中的字符变成字符串, 这里需要 O(L) 的空间
    string windowStr = s.substr(left, 10);
    if (seen.find(windowStr) != seen.end()) {
      // find 
    } else {
      seen.insert(windowStr);
    }

    window.erase(0, 1);
    ++left;
  }
}

这里的优化点在于:
1.我们不要把子字符串生成出来, 而是用某种哈希的方法表示子字符串
2.在滑动过程中, 滑动一次本质也就是最高位删除一位或者最低位增加一位这种操作, window继续哈希
对于1.例如 leetcode 题目 187 要求我们匹配 ACGT 四种字符的且长度为 10 的字符串, 我们可以用一种哈希的方法比如将 ACGT 编码成 0123, 然后就可以执行滑动操作; 这里还有个必须的优化点在于题目中要求模式长度为 10, 那么我们相当于用 10 个 10 进制位来表示, 范围是 pow(10, 10); 这里总共就 4 位字符, 可以按照 4 进制下的 10 数字进行表示, 范围为 pow(4, 10), 范围显著小于 pow(10, 10)

int L = 10;
unordered_set<string> seen;

string window = "";
int left = 0;
int right = 0;
while (right < s.size()) {
  window.push_back(s[right]);
  ++right;

  if (right - left == L) {
    // 获取当前窗口内字符串的哈希值, 时间复杂度O(1)
    int windowHash = window.hash()
    if (seen.find(windowStr) != seen.end()) {
      // find 
    } else {
      seen.insert(windowStr);
    }

    window.erase(0, 1);
    ++left;
  }
}

对于2.滑动过程其实就是上面 [字符串删除最高位和添加到最低位实现方法], 也就是按照进制进行处理, 以 leetcode187 为例给出原题和答案

187.重复的DNA序列

DNA序列 由一系列核苷酸组成,缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。 例如,”ACGAATTCCG” 是一个 DNA序列 。在研究 DNA 时,识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
示例 1:输入:s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 输出:[“AAAAACCCCC”,”CCCCCAAAAA”]

示例 2:输入:s = “AAAAAAAAAAAAA” 输出:[“AAAAAAAAAA”]

class Solution {
 public:
  vector<string> findRepeatedDnaSequences(string s) {
    vector<int> nums(s.size());
    for (int i = 0; i < s.size(); ++i) {
      switch (s[i]) {
        case 'A':
          nums[i] = 0;
          break;
        case 'C':
          nums[i] = 1;
          break;
        case 'G':
          nums[i] = 2;
          break;
        case 'T':
          nums[i] = 3;
          break;
      }
    }
    unordered_set<int> seen;
    unordered_set<string> res;
    vector<string> ans;
    int left = 0;
    int right = 0;
    int windowHash = 0; 
    int L = 10;
    int R = 4;
    int RL = (int) pow(R, L-1);
    while (right < nums.size()) {
      windowHash = R * windowHash + nums[right];
      ++right;

      if (right - left == L) {
        if (seen.find(windowHash) != seen.end()) {
          res.insert(s.substr(left, L));
        } else {
          seen.insert(windowHash);
        }
        windowHash = windowHash - nums[left] * RL;
        ++left;
      }
    }
    ans.assign(res.begin(), res.end());
    return ans;
  }
};

3.Rabin-Karp字符串匹配的执行流程: 基于上述的滑动窗口哈希方法, 我们扩展到一般性地字符串匹配问题, 这里的改动就是将模式串的范围扩大到字符串, 我们先设定为ASCII码这个范围
我们首先对模式串进行哈希, 然后开始滑动窗口哈希, 当判断哈希相等时就完成了匹配过程
4.这里存在一个哈希范围问题, 假设我们对 ASCII 码范围处理是 256, 也就是 256 进制处理; 如果长度为 10 的模式串, 那么需要 pow(256, 10) 才能进行哈希, 这个保存的范围非常大
5.解决单个大数据范的哈希的方法是用一个很大的数字映射到一个较小的范围内, 比如采用求 mod 的方法, 比如模一个很大的素数
6.但是求大数求mod的方法会带来哈希冲突的问题, 导致匹配可能生效, 所以我们需要在哈希判断一致的时候额外再进行一次暴力匹配; 但一般情况下哈希冲突的概率是比较低的, 所以偶尔暴力对整体的时间复杂度几乎不影响
7.两个取模的规则, 但凡涉及到乘法和加法, 通常用以下两个规则进行处理

(X + Y) % Q == (X % Q + Y % Q) % Q
(X * Y) % Q == (X % Q * Y % Q) % Q
X % Q == (X + Q) % Q  // 通常用出现负数的情况, 我们对取模前的数字增加一个模

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

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。

示例 1:输入:haystack = “sadbutsad”, needle = “sad” 输出:0 解释:”sad” 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ,所以返回 0 。

示例 2:输入:haystack = “leetcode”, needle = “leeto” 输出:-1 解释:”leeto” 没有在 “leetcode” 中出现,所以返回 -1 。

class Solution {
 public:
  int strStr(string haystack, string needle) {
    // Rabin-Karp
    int L = needle.size();
    int R = 256;
    const long Q = 9999999967;
    long RL = 1;
    for (int i = 1; i <= L - 1; ++i) {
      // 不停地取模防止溢出
      RL = (RL * R) % Q;
    }
    long needlehHash = 0;
    for (int i = 0; i < needle.size(); ++i) {
      needlehHash = ((R * needlehHash) % Q + (int) needle[i]) % Q;
    }
    long windowHash = 0;
    int left = 0;
    int right = 0;
    while (right < haystack.size()) {
      windowHash = ((R * windowHash) % Q + (int) haystack[right]) % Q;
      ++right;
      if (right - left == L) {
        if (windowHash == needlehHash) {
          if (needle == haystack.substr(left, L)) {
            return left;
          }
        }
        // X % Q == (X + Q) % Q 是一个模运算法则
        // 因为 (windowHash - (haystack[left] * RL) % Q) 可能是负数
        // 所以额外再加一个 Q,保证 windowHash 不会是负数
        windowHash = (windowHash - (haystack[left] * RL) % Q + Q) % Q;
        ++left;
      }
    }
    return -1;
  }
};

转载请注明来源, from goldandrabbit.github.io

💰

×

Help us with donation