RabinKarp 哈希算法：求解《796. 旋转字符串》《459. 重复的子字符串》和《1316. 不同的循环子字符串》

RabinKarp 哈希算法，求解《796. 旋转字符串》《459. 重复的子字符串》和《1316. 不同的循环子字符串》

代码模板

哈希和进制前缀和

const n = s.length, base = new Uint32Array(n), hash = new Uint32Array(n), BASE = 26, MOD = 1e8 + 7 // 字符串长度平方 + 质数
base[0] = 1, hash[0] = s.charCodeAt(0) - 97
for (let i = 1; i < n; i++) {
  base[i] = base[i - 1] * BASE % MOD
  hash[i] = (hash[i - 1] * BASE + s.charCodeAt(0) - 97) % MOD
}

字符串的哈希值

const getRabinKarpHash = (i, len) => {
   if (i === 0) return hash[i + len - 1]
   return (hash[i + len - 1] + MOD - hash[i - 1] * base[len] % MOD) % MOD
}

例题

796. 旋转字符串

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。 s 的 旋转操作 就是将 s 最左边的字符移动到最右边。 例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

答案

RabinKarp 哈希算法

var rotateString = function(s, goal) {
  const n = s.length, BASE = 26, MOD = 1e4 + 7
  if (n !== goal.length) return false
  let sHash = goalHash = 0, base = 1
  for (let i = 0; i < n; i++) {
    sHash = (sHash * BASE + s.charCodeAt(i) - 96) % MOD
    goalHash = (goalHash * BASE + goal.charCodeAt(i) - 96) % MOD
    base = base * BASE % MOD
  }
  for (let k = 0; k < n; k++) {
    sHash = (sHash * BASE + MOD - (s.charCodeAt(k) - 96) * (base - 1) % MOD) % MOD
    if (sHash === goalHash) return true
  }
  return false
};

func rotateString(s string, goal string) bool {
  n := len(s)
  if n != len(goal) {
    return false
  }
  sHash, goalHash, base, BASE, MOD := 0, 0, 1, 26, 10007
  for i := 0; i < n; i++ {
    sHash = (sHash * BASE + int(s[i]) - 96) % MOD
    goalHash = (goalHash * BASE + int(goal[i]) - 96) % MOD
    base = base * BASE % MOD
  }
  for k := 0; k < n; k++ {
    sHash = (sHash * BASE + MOD - (int(s[k]) - 96) * (base - 1) % MOD) % MOD
    if sHash == goalHash {
      return true
    }
  }
  return false
}

459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

答案

RabinKarp 哈希算法

var repeatedSubstringPattern = function(s) {
  const n = s.length, hash = new Uint32Array(n), base = new Uint32Array(n), BASE = 26, MOD = 1e7 + 7
  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 getRabinKarpHash = (i, len) => {
    if (i === 0) return hash[i + len - 1]
    return (hash[i + len - 1] + MOD - hash[i - 1] * base[len] % MOD) % MOD
  }
  next: for (let len = 1; len <= n >> 1; len++) {
    if (n % len !== 0) continue
    for (let i = 0; i + len + len - 1 < n; i += len) {
      h1 = getRabinKarpHash(i, len)
      h2 = getRabinKarpHash(i + len, len)
      if (h1 !== h2) continue next
    }
    return true
  }
  return false
};

func repeatedSubstringPattern(s string) bool {
  n := len(s)
  hash, base, BASE, MOD := make([]int, n), make([]int, n), 26, 10000007
  base[0], hash[0] = 1, 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 getRabinKarpHash func(i int, len int) int
  getRabinKarpHash = func(i int, len int) int {
    if i == 0 {
      return hash[i + len - 1]
    }
    return (hash[i + len - 1] + MOD - hash[i - 1] * base[len] % MOD) % MOD
  }
  next: for len := 1; len <= n >> 1; len++ {
    if n % len != 0 {
      continue
    }
    for i := 0; i + len + len - 1 < n; i++ {
      h1 := getRabinKarpHash(i, len)
      h2 := getRabinKarpHash(i + len, len)
      if h1 != h2 {
        continue next
      }
    }
    return true
  }
  return false
}

1316. 不同的循环子字符串

给你一个字符串 text ，请你返回满足下述条件的 不同 非空子字符串的数目： 可以写成某个字符串与其自身相连接的形式（即，可以写为 a + a，其中 a 是某个字符串）。 例如，abcabc 就是 abc 和它自身连接形成的。

答案

RabinKarp 哈希算法

var distinctEchoSubstrings = function(text) {
  const n = text.length, hash = new Uint32Array(n), base = new Uint32Array(n), BASE = 26, MOD = 10 ** 7 + 7
  base[0] = 1, hash[0] = text.charCodeAt(0) - 96
  for (let i = 1; i < n; i++) {
    base[i] = base[i - 1] * BASE % MOD
    hash[i] = (hash[i - 1] * BASE + text.charCodeAt(i) - 96) % MOD
  }
  const visited = new Set, getRabinKarpHash = (i, len) => {
    if (i === 0) return hash[i + len - 1] % MOD
    return (hash[i + len - 1] + MOD - hash[i - 1] * base[len] % MOD) % MOD
  }
  let ans = 0
  for (let len = 1; len <= n >> 1; len++) {
    for (let i = 0; i + len + len - 1 < n; i++) {
      const h1 = getRabinKarpHash(i, len)
      if (visited.has(h1)) continue
      const h2 = getRabinKarpHash(i + len, len)
      if (h1 === h2) {
        if (text.substring(i, i + len) === text.substring(i + len, i + len + len)) {
          ans++
          visited.add(h1)
        }
      }
    }
  }
  return ans
};

func distinctEchoSubstrings(text string) int {
  n := len(text)
  hash, base, BASE, MOD := make([]int, n), make([]int, n), 26, 10000007
  base[0] = 1
  hash[0] = int(text[0]) - 96
  for i := 1; i < n; i++ {
    base[i] = base[i - 1] * BASE % MOD
    hash[i] = (hash[i - 1] * BASE + int(text[i]) - 96) % MOD
  }
  var value struct{}
  visited, ans := make(map[int]struct{}), 0
  var getRabinKarpHash func(i int, len int) int
  getRabinKarpHash = func(i int, len int) int {
    if i == 0 {
      return hash[i + len - 1]
    } else {
      return (hash[i + len - 1] + MOD - hash[i - 1] * base[len] % MOD) % MOD
    }
  }
  for len := 1; len <= n >> 1; len++ {
    for i := 0; i + len + len - 1 < n; i++ {
      h1 := getRabinKarpHash(i, len)
      if _, ok := visited[h1]; ok {
        continue
      }
      h2 := getRabinKarpHash(i + len, len)
      if (h1 == h2) {
        if text[i : i + len] == text[i + len : i + len + len] {
          ans++
          visited[h1] = value
        }
      }
    }
  }
  return ans
}