串的模式匹配KMP算法

主要基于2019王道数据结构P268-272、2019天勤数据结构P95-101页的讲解，自己整理出来的一套手动计算next数组值、nextval数组值的方法
以下使用的例子是2019王道数据结构P270-271的例子

1.求next

列的3-8是指编号j字符的与原来的字符比较，编号1和2的，直接给定next[1]=0,next[2]=1
①j=3时，比较编号2和1的字符，即b和a，不等，则看next[1]=0，遇到0则是比较到头了，next[j]=1即next[3]=1

②j=4时，比较编号3和1的字符，即a和a，相等，则next[4]=next[3]+1=2

③j=5时，比较编号4和2的字符，即a和b，不等，则看next[2]=1；比较编号4和1，即a和a，相等，next[5]=next[1]+1=2

④j=6时，比较编号5和2的字符，即b和b，相等，则next[6]=next[5]+1=3

⑤j=7时，比较编号6和3的字符，即c和a，不等，则看next[3]=1；比较编号6和1，即c和a，不等，则看next[1]=0,遇到0则是比较到头了，next[j]=1即next[7]=1

⑥j=8时，比较编号7和1的字符，即a和a，相等，则next[8]=next[7]+1=2

如a21只是为了方便记录过程，表示的是所写这一列的后一列即j=3的时候求next的过程，j=3的时候看的是j=2这一列，next[2]=1，所以比较编号2和1的字符，编号1的字符是a故记录a21，和上方的b比较。其实KMP是自己和自己比，但也可以看成是两个一模一样的字符串的比较。

2.求nextval

nextval[0]=0是直接给定的
①j=2时，s[2]=b，s[next[2]]=s[1]=a，不等，nextval[2]=next[2]=1
②j=3时，s[3]=a，s[next[3]]=s[1]=a，相等，nextval[3]=next[next[3]]=next[1]=0，已经追溯到1位置
③j=4时，s[4]=a，s[next[4]]=s[2]=b，不等，nextval[4]=next[4]=2
④j=5时，s[5]=b，s[next[5]]=s[2]=b，相等，nextval[5]=next[next[5]]=next[2]=1，已经追溯到2位置，步骤①证明2位置无法再往前追溯
⑤j=6时，s[6]=c，s[next[6]]=s[3]=a，不等，nextval[6]=next[6]=3
⑥j=7时，s[7]=a，s[next[7]]=s[1]=a，相等，nextval[7]=next[next[7]]=next[1]=0，已经追溯到1位置
⑦j=8时，s[8]=c，s[next[8]]=s[2]=b，不等，nextval[8]=next[8]=2
如步骤⑥，若从7位置追溯到5位置，5位置还能追溯到3位置，3位置才不能在往前追溯，那么nextval[7]=next[3]