KMP 算法:求解《28. 实现 strStr()》《1392. 最长快乐前缀》和《214. 最短回文串》

2022-04-21 20:56:18
Knuth - Morris - Pratt 算法,求解《28. 实现 strStr()》《1392. 最长快乐前缀》和《214. 最短回文串》

KMP 算法求解 next 数组计算步骤示意图

Kunth - Morris - Pratt 算法(KMP 算法)模板代码

例题

28. 实现 strStr()

实现 strStr() 函数。 给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1 。

答案

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

var strStr = function(haystack, needle) {
  const m = needle.length
  const next = new Uint16Array(m)
  for (let i = 1, j = 0; i < m; i++) {
    while (j > 0 && needle[i] !== needle[j]) j = next[j - 1]
    if (needle[i] === needle[j]) j++
    next[i] = j
  }
  const n = haystack.length
  for (let i = 0, j = 0; i < n; i++) {
    while (j > 0 && haystack[i] !== needle[j]) j = next[j - 1]
    if (haystack[i] === needle[j]) j++

    if (j === m) return i - m + 1
  }
  return -1
};
func strStr(haystack string, needle string) int {
  m, n := len(needle), len(haystack)
  next := make([]int, m)
  for i, j := 1, 0; i < m; i++ {
    for j > 0 && needle[i] != needle[j] {
      j = next[j - 1]
    }
    if needle[i] == needle[j] {
      j++
    }
    next[i] = j
  }
  for i, j := 0, 0; i < n; i++ {
    for j > 0 && haystack[i] != needle[j] {
      j = next[j - 1]
    }
    if haystack[i] == needle[j] {
      j++
    }

    if j == m {
      return i - m + 1
    }
  }
  return -1
}

1392. 最长快乐前缀

「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀(不包括原字符串自身)的字符串。 给你一个字符串 s,请你返回它的 最长快乐前缀。如果不存在满足题意的前缀,则返回一个空字符串 "" 。

答案

Kunth-Morris-Pratt 算法(KMP 算法)
var longestPrefix = function(s) {
  const n = s.length
  const next = new Uint32Array(n)
  for (let i = 1, j = 0; i < n; i++) {
    while (j > 0 && s[i] !== s[j]) j = next[j - 1]
    if (s[i] === s[j]) j++
    next[i] = j
  }
  return s.substring(0, next[n - 1])
};
func longestPrefix(s string) string {
  n := len(s)
  next := make([]int, n)
  for i, j := 1, 0; i < n; i++ {
    for j > 0 && s[i] != s[j] {
      j = next[j - 1]
    }
    if s[i] == s[j] {
      j++
    }
    next[i] = j
  }
  return s[:next[n - 1]]
}

214. 最短回文串

给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

答案

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

var shortestPalindrome = function(s) {
  const n = s.length, next = new Uint16Array(n)
  for (let i = 1, j = 0; i < n; i++) {
    while (j > 0 && s[i] !== s[j]) j = next[j - 1]
    if (s[i] == s[j]) j++
    next[i] = j
  }
  let j = 0
  for (let i = n; i--;) {
    while (j > 0 && s[i] !== s[j]) j = next[j - 1]
    if (s[i] == s[j]) j++
  }
  return s.substring(j).split('').reverse().join('') + s
};
func shortestPalindrome(s string) string {
  n := len(s)
  next := make([]int, n)
  for i, j := 1, 0; i < n; i++ {
    for j > 0 && s[i] != s[j] {
      j = next[j - 1]
    }
    if s[i] == s[j] {
      j++
    }
    next[i] = j
  }
  j := 0
  for i := n - 1; i >= 0; i-- {
    if j > 0 && s[i] != s[j] {
      j = next[j - 1]
    }
    if s[i] == s[j] {
      j++
    }
  }
  return reverse(s[j:]) + s
}
func reverse (s string) string {
  n := len(s)
  b := []byte(s)
  for i := 0; i < n / 2; i++ {
    b[i], b[n - i - 1] = b[n - i - 1], b[i]
  }
  return string(b)
}
自定义排序:求解《937. 重新排列日志文件》
自定义排序和 Golang 的字符串分割函数,求解《937. 重新排列日志文件》
消元法,正则和栈:求解《591. 标签验证器》
消元法,正则和栈,求解《591. 标签验证器》
RabinKarp 哈希算法:求解《796. 旋转字符串》《459. 重复的子字符串》和《1316. 不同的循环子字符串》
RabinKarp 哈希算法,求解《796. 旋转字符串》《459. 重复的子字符串》和《1316. 不同的循环子字符串》