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

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