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

代码数据结构:字符串算法:KMP 语言:JavaScript 语言:Go 语言:PHP

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 数组

一定有最长相同前后缀：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;
}
}

1316. 不同的循环子字符串

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

答案

Knuth - Morris -Pratt 算法（KMP 算法）

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