代码随想录算法训练营第8天 | lc28、lc459-526互联

（本合集全部为Go语言实现）

相关文章链接：28题解 459题解
相关视频链接：

Leetcode28

状态：每次看都有新体验，稍微耗了些时间复习了一下
实现过程中的难点：主要还是KMP算法，对于这种经典的算法，能理解代码含义当然是一方面，自我感觉还是得稍微一点时间在看懂一套实现之后稍微背一下代码，这种比较复杂的算法在比如面试或笔试的时候，时间紧迫的情况下确实没必要现推，比较浪费时间而且不一定写的对

个人写法

以下是我个人比较推荐的一套代码，比较简洁但是可能理解的成本稍微高一点
需要注意的是，首元素不同的两种情况下，查找主体函数的写法也有所不同，主要在于模式串当前位失配之后是回溯到next数组的当前位值（-1的写法）还是前一位值（0的写法）

首元素为`-1`的写法

func next(pattern str) []int {
  next := make([]int, len(pattern))
  i, j := 1, 0
  next[0] = -1
  for i < len(pattern) - 1 {
    if j == -1 || pattern[i] == pattern[j] {
      i++
      j++
      next[i] = j
    } else {
      j = next[j]
    }
  }
  return next
}

func nextVal(pattern str) []int {
  arr := []byte(pattern)
  nextVal := make([]int, len(pattern))
  nextVal[0] = -1
  i, j := 0, -1
  for i < len(pattern)-1 {
    if j == -1 || arr[i] == arr[j] {
      i++
      j++
      if arr[i] != arr[j] {
        nextVal[i] = j
      } else {
        nextVal[i] = nextVal[j]
      }
    } else {
      j = nextVal[j]
    }
  }
  return nextVal
}

首元素为`0`的写法

func next(pattern string) []int {
  arr := []byte(pattern)
  next := make([]int, len(pattern))
  next[0] = 0
  i, j := 1, 0
  for i < len(pattern) {
    if arr[i] == arr[j] {
      j++
      next[i] = j
      i++
    } else {
      if j != 0 {
        j = next[j-1]
      } else {
        next[i] = 0
        i++
      }
    }
  }
  return next
}

func nextVal(pattern string) []int {
  arr := []byte(pattern)
  nextVal := make([]int, len(pattern))
  nextVal[0] = 0
  i, j := 1, 0
  for i < len(pattern) {
    if arr[i] == arr[j] {
      j++
      if arr[i] != arr[j] {
        nextVal[i] = j
      } else {
        nextVal[i] = nextVal[j]
      }
      i++
    } else {
      if j != 0 {
        j = nextVal[j-1]
      } else {
        nextVal[i] = 0
        i++
      }
    }
  }
  return nextVal
}

Leetcode459

状态：稍微有点印象，但是忘了解决方法和思路了，看了题解之后可以看明白
实现过程中的难点：确实还是得想到KMP的思路，否则基本就是暴力解

个人写法

func repeatedSubstringPattern(s string) bool {
  next := make([]int, len(s))
  i, j := 1, 0
  next[0] = -1
  for i < len(s) - 1 {
    if j == -1 || s[i] == s[j] {
      i++
      j++
      next[i] = j
    } else {
      j = next[j]
    }
  }
  if next[len(s) - 1] != -1 && s[next[len(s) - 1]] == s[len(s) - 1] {
    return len(s) % (len(s) - next[len(s) - 1] - 1) == 0
  } else {
    return false
  }
}