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

2022-04-23 21:07:40
Knuth - Morris - Pratt 算法(KMP算法),求解《796. 旋转字符串》《459. 重复的子字符串》和《1316. 不同的循环子字符串》

判断目标字符串可旋转或有循环字串构成的 JavaScript 代码模板

PHP 创建初始值为 0 的数组

$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)
};

例题

796. 旋转字符串

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

答案

Knuth - Morris - Pratt 算法(KMP 算法)

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;
    }
}

459. 重复的子字符串

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

答案

Knuth - Morris - Pratt 算法(KMP 算法)

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;
    }
}

Knuth - Morris - Pratt 算法(KMP 算法) 优化

判断 next 数组

顺序遍历字符串,双指针技巧,用 startsWith (javascript / typescript / java) / StartsWith (c#) / startswith (python) / str_starts_with (php) / strings.HasPrefix (golang)接口,求解《1455. 检查单词是否为句中其他单词的前缀》
顺序遍历字符串,双指针技巧,用 startsWith (javascript / typescript / java) / StartsWith (c#) / startswith (python) / str_starts_with (php) / strings.HasPrefix (golang)接口,求解《1455. 检查单词是否为句中其他单词的前缀》
顺序遍历,计数和奇偶性交换 2 种算法,求解《1417. 重新格式化字符串》
顺序遍历,计数和奇偶性交换 2 种算法,用双指针技巧,求解《1417. 重新格式化字符串》
顺序遍历,数字转字符串,求解《640. 求解方程》
顺序遍历,str / strconv.Itoa / sprintf(_, "x=%d", 1) / to_string 数字转字符串,求解《640. 求解方程》