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

Knuth - Morris - Pratt 算法，求解《28. 实现 strStr()》《1392. 最长快乐前缀》和《214. 最短回文串》

Kunth - Morris - Pratt 算法（KMP 算法）模板代码

• 求 next 数组

  const m = p.length, next = new Uint32Array(m)
  for (let i = 1, j = 0; i < m; i++) {
  while (j > 0 && p[i] !== p[j]) j = next[j - 1]
  if (p[i] === p[j]) j++
  next[i] = j
  }

• 匹配模式字符串

  const n = s.length
  for (let i = 0, j = 0; i < n; i++) {
  while (j > 0 && s[i] !== p[j]) j = next[j - 1]
  if (s[i] === p[j]) j++
  if (j === m) { // i - m + 1 即索引起始位置 }
  }

例题

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