求字符串‘abaabcac’的next数组和nextval数组

今天刷到一个笔试题，求一个字符串在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
• 同理，可以求出所有的啦

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