$next = array_fill(0, n, 0);
var rotateString = function(s, goal) {
return s.length === goal.length && (s + s).includes(goal)
};
[1, n - 1]
次匹配自身var repeatedSubstringPattern = function(s) {
return (s + s).slice(1, -1).includes(s)
};
给定两个字符串, s 和 goal。如果在若干次旋转操作之后,s 能变成 goal ,那么返回 true 。 s 的 旋转操作 就是将 s 最左边的字符移动到最右边。 例如, 若 s = 'abcde',在旋转一次之后结果就是'bcdea' 。
var rotateString = function(s, goal) {
const m = goal.length, n = s.length, next = new Uint8Array(m)
if (m !== n) return false
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && goal[i] !== goal[j]) j = next[j - 1]
if (goal[i] === goal[j]) j++
next[i] = j
}
for (let i = 0, j = 0; i < n << 1; i++) {
while (j > 0 && s[i % n] !== goal[j]) j = next[j - 1]
if (s[i % n] === goal[j]) j++
if (j === m) return true
}
return false
};
func rotateString(s string, goal string) bool {
m, n := len(goal), len(s)
if m != n {
return false
}
next := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && goal[i] != goal[j] {
j = next[j - 1]
}
if goal[i] == goal[j] {
j++
}
next[i] = j
}
for i, j := 0, 0; i < n << 1; i++ {
for j > 0 && s[i % n] != goal[j] {
j = next[j - 1]
}
if s[i % n] == goal[j] {
j++
}
if j == m {
return true
}
}
return false
}
class Solution {
function rotateString($s, $goal) {
$m = strlen($goal);
$n = strlen($s);
if ($m !== $n) return false;
$next = array_fill(0, $m, 0);
for ($i = 1, $j = 0; $i < $m; $i++) {
while ($j > 0 && $goal[$i] !== $goal[$j]) $j = $next[$j - 1];
if ($goal[$i] === $goal[$j]) $j++;
$next[$i] = $j;
}
for ($i = 0, $j = 0; $i < $n << 1; $i++) {
while ($j > 0 && $s[$i % $n] !== $goal[$j]) $j = $next[$j - 1];
if ($s[$i % $n] === $goal[$j]) $j++;
if ($j === $m) return true;
}
return false;
}
}
给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。
var repeatedSubstringPattern = function(s) {
const m = s.length, next = new Uint16Array(m)
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && s[i] !== s[j]) j = next[j - 1]
if (s[i] === s[j]) j++
next[i] = j
}
for (let i = 1, j = 0; i < (m << 1) - 1; i++) {
while (j > 0 && s[i % m] !== s[j]) j = next[j - 1]
if (s[i % m] === s[j]) j++
if (j === m) return true
}
return false
};
func repeatedSubstringPattern(s string) bool {
m := len(s)
next := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && s[i] != s[j] {
j = next[j - 1]
}
if s[i] == s[j] {
j++
}
next[i] = j
}
for i, j := 1, 0; i < (m << 1) - 1; i++ {
for j > 0 && s[i % m] != s[j] {
j = next[j - 1]
}
if s[i % m] == s[j] {
j++
}
if j == m {
return true
}
}
return false
}
class Solution {
function repeatedSubstringPattern($s) {
$m = strlen($s);
$next = array_fill(0, $m, 0);
for ($i = 1, $j = 0; $i < $m; $i++) {
while ($j > 0 && $s[$i] !== $s[$j]) $j = $next[$j - 1];
if ($s[$i] === $s[$j]) $j++;
$next[$i] = $j;
}
for ($i = 1, $j = 0; $i < ($m << 1) - 1; $i++) {
while ($j > 0 && $s[$i % $m] !== $s[$j]) $j = $next[$j - 1];
if ($s[$i % $m] == $s[$j]) $j++;
if ($j === $m) return true;
}
return false;
}
}
判断 next
数组
next[m - 1] > 0
m
可整除长度m
减去最长相同前后缀
var repeatedSubstringPattern = function(s) {
const m = s.length, next = new Uint16Array(m)
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && s[i] !== s[j]) j = next[j - 1]
if (s[i] === s[j]) j++
next[i] = j
}
return next[m - 1] > 0 && m % (m - next[m - 1]) === 0
};
func repeatedSubstringPattern(s string) bool {
m := len(s)
next := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && s[i] != s[j] {
j = next[j - 1]
}
if s[i] == s[j] {
j++
}
next[i] = j
}
return next[m - 1] > 0 && m % (m - next[m - 1]) == 0
}
class Solution {
function repeatedSubstringPattern($s) {
$m = strlen($s);
$next = array_fill(0, $m, 0);
for ($i = 1, $j = 0; $i < $m; $i++) {
while ($j > 0 && $s[$i] !== $s[$j]) $j = $next[$j - 1];
if ($s[$i] === $s[$j]) $j++;
$next[$i] = $j;
}
return $next[$m - 1] > 0 && $m % ($m - $next[$m - 1]) === 0;
}
}
给你一个字符串 text ,请你返回满足下述条件的 不同 非空子字符串的数目: 可以写成某个字符串与其自身相连接的形式(即,可以写为 a + a,其中 a 是某个字符串)。 例如,abcabc 就是 abc 和它自身连接形成的。
var distinctEchoSubstrings = function(text) {
const n = text.length
let ans = 0
for (let len = 2; len <= n; len += 2) {
const visited = new Set
for (let start = 0; start + len - 1 < n; start++) {
const s = text.slice(start, start + len)
if (visited.has(s)) continue
const next = new Uint16Array(len)
for (let i = 1, j = 0; i < len; i++) {
while (j > 0 && s[i] !== s[j]) j = next[j - 1]
if (s[i] === s[j]) j++
next[i] = j
}
if (next[len - 1] > 0 && len % (len - next[len - 1]) === 0 && len / (len - next[len - 1]) % 2 === 0) {
ans++
visited.add(s)
}
}
}
return ans
};