今天刷到一个笔试题，求一个字符串在KMP算法下的next数组和nextval数组

几番百度和看题解，居然大多数的题解都有毛病被一顿吐槽

几番周折终于搞懂了怎么求next数组和nextval数组，在此记录下

题目是：

求字符串abaabcac的next数组和nextval数组：

结果如下：

注意： 这里的数组下标从1开始数

首先，通过一个动图来了解下求next数组的过程


本图来自这个博客

我觉得这张图已经很直观了，下面我就对求解的方法做一点自己的总结

求next数组
  • next[1] = 0
  • next[2] = 1
  • 当i > 2 时，如：求next[5]
    • 求next[0]~next[i - 1]所构成的串的首子串和尾子串（首子串不包括最后一个，尾子串不包括第一个）
      next[0]~next[4]为：abaa
      首子串：a，ab，aba
      尾子串：baa，aa，a
    • 计算首尾子串中相同的子串的长度
      相同的子串为a，长度为1
    • next[i] = length + 1
      求得长度为1,1+1 = 2，所以next[5] = 2
求nextval数组
  • 求nextval[i]的值，我们要比较String[i]和String[next[i]]的值
    • 如果String[i]和String[next[i]]的字符相等，那么nextval[i]的值就等于nextval[next[i]]的值，
    • 如果String[i]和String[next[i]]的字符不相等，那么nextval[i]的值就等于next[i]的值。

就上面的串进行演示：

  • i = 1
    nextval[1] = 0
  • i = 2
    nextval[2] = 1
  • i = 3
    next[3] = 1
    String[3] = a
    String[1] =a == a
    nextval3] = nextval[1] = 0
  • i = 4
    next[4] = 2
    String[4] = a
    String[2] = b != a
    nextval[4] = next[4] = 2
  • 同理，可以求出所有的啦

花了一个多小时百度和总结，有了比较深刻的印象了，下次遇到就能轻松应对了