KMP模式匹配算法

next数组：寻找子串的子串 的 相同前缀和后缀的长度

  1. 例子：子串abcabx
  2. -1 
  3.  0 a 
  4.  0 a b
  5.  0 a b c
  6.  1 a b c a
  7.  2 a b c a b
  9.    0 1 2 3 4 5
  10.    a b c a b x
  11.   -1 0 0 0 1 2  //回溯开始比较的位置，第一个元素下标为0，-1表示后移一位比较。
  13. 左边为最短子串前后缀的长度，前后缀不能相同，只能相等。
  14. eg aaaa，最长的前后缀长度为3

子串比较主串，根据next数组回溯到相应位置，可以大大增加效率。
大佬的视频教程
点击查看【bilibili】

KMP匹配算法改进

问题
当主串S=”aaaabcde”,子串T=”aaaaax”时。next为-101234
此时会回溯四次而无法匹配。

求nextval数组的数值

  1. 第一个等于0，第二个如果相等等于nextval[2]=nextval[1]=-1,如果不相等nextval[2]=next[2];
  2. 然后后面的都和前面隔一位比较相同则nextval[n]=nextval[n-2]，不同则nextval[n]=next[n]