RabinKarp 哈希算法、二分查找：求解《1044. 最长重复子串》

用 RabinKarp 哈希算法和二分查找，求解《1044. 最长重复子串》

Rabin Karp 哈希算法

• 进制base 多少种
• 模MOD 长度的平方 + 质数（7 / 9）
• 字符转数字时，减 96 ，而不是 97，避免出现 0 乘以 base

取余后，哈希相减为负

• ( 被减数 + MOD - 减数 % MOD ) % MOD

取余后，哈希冲突

• 双哈希：设置两个进制 base
• 冲突后：用其它方式辅助验证

例题

1044. 最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。 返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

答案

Rabin Karp 哈希算法 · 二分查找

枚举重复字符串长度，用 Rabin Karp 判断该长度下有无字符串重复

var longestDupSubstring = function(s) {
  const n = s.length, hash = new Uint32Array(n), base = new Uint32Array(n), BASE = 26, MOD = 1e8 + 9
  base[0] = 1, hash[0] = s.charCodeAt(0) - 96
  for (let i = 1; i < n; i++) {
    base[i] = base[i - 1] * BASE % MOD
    hash[i] = (hash[i - 1] * BASE + s.charCodeAt(i) - 96) % MOD
  }
  const rabinHash = len => {
    const map = new Map()
    for (let i = 0; i + len - 1 < n; i++) {
      const h = (hash[i + len - 1] + MOD - (i > 0 ? hash[i - 1] * base[len] : 0) % MOD) % MOD
      if (map.has(h)) {
        const iPre = map.get(h), t = s.substring(i, i + len)
        if (t === s.substring(iPre, iPre + len)) return t
      }
      map.set(h, i)
    }
    return ''
  }
  let l = 0, r = n - 1, t = ans = ''
  while (l < r) {
    const m = l + r + 1 >> 1
    if (t = rabinHash(m)) {
      l = m
      if (t.length > ans.length) ans = t
    } else r = m - 1
  }
  return ans
};

func longestDupSubstring(s string) string {
  n := len(s)
  hash, base, BASE, MOD := make([]int, n), make([]int, n), 26, 100000007
  base[0] = 1
  hash[0] = int(s[0]) - 96
  for i := 1; i < n; i++ {
    base[i] = base[i - 1] * BASE % MOD
    hash[i] = (hash[i - 1] * BASE + int(s[i]) - 96) % MOD
  }
  var rabinHash func (len int) string
  rabinHash = func (len int) string {
    set := make(map[int]int)
    for i := 0; i + len - 1 < n; i++ {
      h := 0
      if (i == 0) {
        h = hash[i + len - 1]
      } else {
        h = hash[i + len - 1] + MOD - hash[i - 1] * base[len] % MOD
      }
      h %= MOD
      if iPre, ok := set[h]; ok {
        t := s[iPre : iPre + len]
        if t == s[i : i + len] {
          return t
        } 
      }
      set[h] = i
    }
    return ""
  }
  l, r, ans := 0, len(s) - 1, ""
  for l < r {
    m := (l + r + 1) >> 1
    t := rabinHash(m)
    if t != "" {
      l = m
      if len(t) > len(ans) {
        ans = t
      }
    } else {
      r = m - 1
    }
  }
  return ans
}