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
}
给定两个字符串, s 和 goal。如果在若干次旋转操作之后,s 能变成 goal ,那么返回 true 。 s 的 旋转操作 就是将 s 最左边的字符移动到最右边。 例如, 若 s = 'abcde',在旋转一次之后结果就是'bcdea' 。
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
}
给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。
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
}
给你一个字符串 text ,请你返回满足下述条件的 不同 非空子字符串的数目: 可以写成某个字符串与其自身相连接的形式(即,可以写为 a + a,其中 a 是某个字符串)。 例如,abcabc 就是 abc 和它自身连接形成的。
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
}