Rabin-Karp算法

基于《算法（第四版）》Rabin-Karp算法实现的

Rabin-Karp指纹字符串查找算法是一种基于哈希的字符串查找算法。我们需要计算模式串的哈希函数，然后利用相同的哈希函数计算文本中所有可能的M个字符的子字符串哈希值并寻找匹配。如果找到了一个哈希值和模式串相同的子字符串，那么继续沿着两者是否匹配。如果直接计算每个字字符串的哈希值进行查找，其实现的算法会比暴力子字符串查找算法慢很多。Rabin和Karp发明了一种能在常数时间内计算出M个字符的子字符串哈希值的方法（需要预处理），这样就得到了在实际应用中运行时间为线性级别的字符串查找算法。

基本思路

长度为M的字符串对应着一个R进制的M位数。取一个随机的质数Q，在不溢出的情况下选择一个尽可能大的值。哈希函数会将一个R进制的M位数转化为一个0到Q-1的整数。以R=10的情况下，在文本”3141592653589793”中找到模式”26535”，首先选择一个质数Q，这里为997，则模式哈希值为26535 % 997 = 613，然后计算文本中所有长度为5的子字符串的哈希值并寻找匹配。

计算哈希函数

函数使用Horner方法，具体对每一个数字，将哈希值乘以R，加上这个数字，除以Q并取其余数。

// Horner方法，用于除留余数法计算哈希值。
function hash(key, M) {
    // 计算k[0, M-1]的哈希值
  let h = 0;
  for (let j = 0; j < M; j += 1) {
      h = (h * R + key.charCodeAt(j)) % Q;
  }
  return h;
}

关键思路

Rabin-Karp算法的基础是对于所有i，高级计算文本中i+1位置的子字符串哈希值，可以通过一个数学公式得到。用 t(i)表示 txt.charCodeAt(i)，那么文本中起始于位置i的含有M个字符的子字符串所对应的数为：
x(i) = t(i) R^(M-1) + ti+1 R^(M-2) + … + t(i+M-1)R^0
假设已知h(x(i)) = x(i) % Q。将模式字符串右移一位即等价于将x(i)替换为：
x(i+1) = (x(i) - t(i) R^(M-1)) R + t(i+M)
即*将它减去第一个数字的值，乘以R，再加上最后一个数字的值。关键一点是，我们不需要保存这些数的值，只需要保存它们除以Q并取余，这等价于再完成了所有算数操作再将最后的结果除以Q并取余。这样就可以在常数时间内高效地不断向右一格一格地移动。

代码实现

function search(pat, txt) {
  const M = pat.length
  const N = txt.length
  const Q = longRandomPrime()
  const R = 256
  let RM = 1 // R^(M-1)%Q
  for (let i = 1; i <= M - 1; i += 1) {
    RM = (R * RM) % Q
  }
  const patHash = hash(pat, M)
  let txtHash = hash(txt, M)
  if (patHash === txtHash && check(0)) return 0 // 一开始就匹配
  for (let i = M; i < N; i += 1) {
    // 额外加上一个Q来保证所有的数均为整数，这样取余操作才能够能到预期的结果。
    txtHash = (txtHash + Q - ((txt.charCodeAt(i - M) * RM) % Q)) % Q
    txtHash = (txtHash * R + txt.charCodeAt(i)) % Q
    if (patHash === txtHash) {
      if (check(i - M + 1)) return i - M + 1 // 找到匹配
    }
  }
  return -1 // 未找找到
  function hash(key, M) {
    let h = 0
    for (let j = 0; j < M; j += 1) {
      h = (h * R + key.charCodeAt(j)) % Q
    }
    return h
  }
  // 蒙特卡洛算法，总是返回true，有失败的概率
  // function check(i) {
  //   return true;
  // }
  // 拉斯维加斯算法，速度慢，但保证了准确性
  function check(i) {
    for (let j = 0; j < M; j += 1) {
      if (pat.charCodeAt(j) !== txt.charCodeAt(i + j)) {
        return false
      }
    }
    return true
  }
  // TODO: 随机一个很大的素数，这里先写死
  function longRandomPrime() {
    return 993
  }
}