kmp算法

关键概念

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。

j和next[0]初始化为-1，整个next数组是以 前缀表减一之后的效果来构建的

时间复杂度

生成next数组，时间复杂度是O (m), 后续匹配过程时间复杂度是O（n），时间复杂度是O(m+n)

暴力解法是O(m*n)

构建next数组

1. 初始化

定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置。

2. 处理前后缀不相同的情况: 回退
3. 处理前后缀相同的情况： j++

const getNext = function(s) {
  let next = []
  let j = -1
  next[0] = j
  for(let i = 1; i < s.length; i++) {
    while(j >= 0 && s[j+1] !== s[i]){ // s[j + 1] 与 s[i] 不相等
      j = next[j] // 回退
        // next[j]就是记录着j（包括j）之前的子串的最长相同前后缀的长度。
    }
    if(s[j+1] === s[i]) j++  //找到了相同的前后缀，同时向后移动i、j
    next[i] = j  // 将j(前缀的长度)赋给next[i],next[i]记录最长相同前后缀的长度
  }
  return next //f
}

let strStr = function(haystack, needle) {
  if(needle.length === 0) return 0
  const getNext = function(s) {
    let next = []
    let j = -1
    next[0] = j
    for(let i = 1; i < s.length; i++) {
      while(j >= 0 && s[j+1] !== s[i]){
        j = next[j]
      }
      if(s[j+1] === s[i]) j++
      next[i] = j 
    }
    return next
  }
  
  let next = getNext(next, needle)
  let j = -1
  for(let i = 0; i < haystack.length; i++) {
    while(j >= 0 && haystack[i] !== needle[j+1]){
      j = next[j]
    }
    if(haystack[i] === needle[j+1]) j++
    if(j === needle.length - 1) {
      return i - needle.length + 1
    }
  }
  return -1
}

leetcode

459. 重复的子字符串

function repeatedSubstringPattern(s: string): boolean {
    const getNext = (s) => {
        let j = -1
        let next = [j]
        for(let i = 1; i < s.length; i++) {
            while(j >= 0 && s[j+1] !== s[i]) {
                j = next[j]
            }
            if(s[j+1] === s[i]){
                j++
            }
            next[i] = j
        }
        return next
    }
    if(s.length === 0) return false
    let next = getNext(s)
    if(next[s.length - 1] !== -1 && s.length % (s.length - (next[s.length - 1] + 1)) === 0) {
        return true
    }
    return false
};