RabinKarp 哈希算法：字符串转任意进制，多变量转唯一键名

RabinKarp 哈希算法，将字符串转换为任意进制数字，或将多变量转换为唯一键名，可用于匹配、记忆化递归剪枝等。

字符串转换任意进制

将字符串转换为任意进制base，base >= 2

代码

方法一：前缀和

• 转换结果会超过安全整数范围，建议取模 10 ** 9 + 7 或 10 ** 9 + 9

function rabinKarpHash(str, base) {
  const n = str.length, MOD = 10 ** 9 + 7
  let sum = 0
  for (let i = 0; i < n; i++) {
    sum = sum * base + str.charCodeAt(i) 
    sum %= MOD
  }
  return sum
}

测试

console.log(rabinKarpHash('aa', 10)) // 1067 = 970 + 97 

方法二：后缀和

• 使用幂运算，进制的次方，有可能超过安全整数范围，带来精度误差
• 避免使用幂运算，新建一个变量，存储累乘的结果，并对该结果取模

function rabinKarpHash(str, base) {
  const n = str.length, MOD = 10 ** 9 + 7
  let sum = 0, baseNew = 1
  for (let i = 0; i < n; i++) {
    sum += str.charCodeAt(n - i - 1) * baseNew
    sum %= MOD
    baseNew *= base
    baseNew %= MOD // 对新进制取模，避免使用幂运算
  }
  return sum
}

测试

console.log(rabinKarpHash('aa', 10)) // 1067 = 97 + 970

例题

1392. 最长快乐前缀

「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。 给你一个字符串 s，请你返回它的 最长快乐前缀。如果不存在满足题意的前缀，则返回一个空字符串 "" 。

答案

var longestPrefix = function(s) {
  const n = s.length, base = 27, MOD = 10 ** 9 + 7
  let prefixSum = suffixSum = 0
  for (let i = 0; i < n; i++) {
    prefixSum = prefixSum * base + s.charCodeAt(i)
    prefixSum %= MOD
    suffixSum += s.charCodeAt(i) * base ** (n - i - 1)
    suffixSum %= MOD
    if (prefixSum === suffixSum) return 
  }
};

多变量生成唯一键名

已知多个变量，需要生成唯一键名，存入哈希表，用于记忆化递归剪枝

• 将变量顺序排列
• 唯一键名 += 前面的变量 * 后面的变量的范围 + 后面的变量

代码

// 伪代码：多变量生成唯一键名
function uniqueHash(... a, b, c) {
  return ... + a * b (范围) * c(范围) + b * (c)范围 + c
} 

例题

188. 买卖股票的最佳时机 IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

答案

这道题有多解法，本文用递归法解题，并用多变量生成哈希表唯一键名的方法剪枝

var maxProfit = function(k, prices) {
  const n = prices.length, h = new Map
  const d = (i, j, s) => {
    const uniqueKey = getUniqueKey(i, j ,s)
    if (h.get(uniqueKey) !== void 0) return h.get(uniqueKey)
    if (i === n || j === k) return 0
    h.set(uniqueKey, s === true ? Math.max(d(i + 1, j, s), d(i + 1, j + 1, false) + prices[i])
                                : Math.max(d(i + 1, j, s), d(i + 1, j, true) - prices[i]))
    return h.get(uniqueKey)
  }
  return d(0, 0, false)
};
const getUniqueKey = (i, j, s) => i * 1001 * 2 + j * 2 + s // s 的范围是 2( 2 状态：持有 / 没有)，j 的范围 1001(k ∈ [0, 1000])