RabinKarp 哈希算法：求解《1392. 最长快乐前缀》和《214. 最短回文串》

RabinKarp 哈希算法

• base: 字符串中可能出现的字符种类的数目
• MOD：字符串长度平方

例题

1392. 最长快乐前缀

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

答案

RabinKarp 哈希算法

比较前缀和后缀

var longestPrefix = function(s) {
  const n = s.length, MOD = 10 ** 9 + 7, base = 26
  let prefix = suffix = 0, r = -1, baseNew = 1
  for (let i = 0; i < n - 1; i++) {
    prefix = prefix * base + s.charCodeAt(i)
    prefix %= MOD
    suffix = s.charCodeAt(n - i - 1) * baseNew  + suffix
    suffix %= MOD
    baseNew *= base
    baseNew %= MOD
    if (prefix === suffix) r = i
  }
  return s.substring(0, r + 1)
};

func longestPrefix(s string) string {
  n, base, baseNew, MOD, maxIndex, prefix, suffix := len(s), 26, 1, 1000000007, -1, 0, 0
  for i := 0; i < n - 1; i++ {
    prefix = prefix * base + int(s[i])
    prefix %= MOD
    suffix = int(s[n - i - 1]) * baseNew + suffix
    suffix %= MOD
    baseNew *= base
    baseNew %= MOD 
    if prefix == suffix {
      maxIndex = i
    }
  }
  return s[:maxIndex + 1]
}

214. 最短回文串

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

答案

RabinKarp 哈希算法

比较字符串和它的翻转

var shortestPalindrome = function(s) {
  const n = s.length, base = 26, MOD = 10 ** 8 + 7
  let left = right = 0, baseNew = 1, maxIndex = 0
  for (let i  = 0; i < n; i++) {
    left = left * base  + s.charCodeAt(i)
    left %= MOD
    right = s.charCodeAt(i) * baseNew + right
    right %= MOD
    baseNew *= base
    baseNew %= MOD
    if (left === right) {
      maxIndex = i
    }
  }
  return s.substring(maxIndex + 1).split('').reverse().join('') + s
};

func shortestPalindrome(s string) string {
  if s == "" {
    return ""
  }
  n, base, baseNew, MOD, left, right, maxIndex := len(s), 26, 1, 100000007, 0, 0, 0
  for i := 0; i < n; i++ {
    left = left * base + int(s[i])
    left %= MOD
    right = int(s[i]) * baseNew + right
    right %= MOD
    baseNew *= base
    baseNew %= MOD
    if left == right {
      maxIndex = i
    }
  }
  return reverse(s[maxIndex + 1:]) + s
}
func reverse(s string) string {
  b := []byte(s)
  n := len(b)
  for i := 0; i < n / 2; i++ {
    b[i], b[n - i - 1] = b[n - i - 1], b[i]
  }
  return string(b)
}