前言
在学习串这一章节时，只有KMP算法让人伤脑筋，它的代码对我来说有种就差一点就能通透的感觉(现在是2024/4/7/还没彻底通透)
那就先放一下，这章的主要考点是求next数组和优化后的nextval数组，所以本篇只讲怎么求
本篇都是以坐标从1开始的串为例
干货
next数组
一个公式：next[j] = j左边子串的匹配数+1
所谓的匹配就是前面（必须包含首字符）和后面（必须包含尾字符）重复的最长子串的长度，类似"a"、“ab”、"ba"这种视为匹配数为0（了解意思就好）
看不懂？没关系
实操一下
假设一个串是“ababaaababaa”(假设字符坐标从1开始)，next[1]=0。
“|”左边是匹配的子串，“|”右边是匹配失败的那个字符。
- next[2]=? a|b… “|”的左边只有一个字符a，所以匹配数为0，next[2]=0+1=1;
- next[3]=? ab|a… “|”的左边有两个字符，ab只有自身可以匹配，所以匹配数为0，next[3]=0+1=1;
- next[4]=? aba|b… “|”的左边有三个字符，aba的最前面1个和最后面1个字符匹配，所以匹配数为1，next[4]=1+1=2;
- next[5]=? abab|a… “|”的左边有abab四个字符，abab前两个和后两个匹配，匹配数为2，next[5]=2+1=3;
- next[6]=? ababa|a… “|”的左边有ababa五个字符，ababa前3个和后3个匹配，匹配数为3，next[6]=3+1=4;
- next[7]=? ababaa|a… “|”的左边有ababaa六个字符，ababaa最前面1个和最后面1个字符匹配，匹配数为1，next[7]=1+1=2;
- …
- 剩下的推理方式相同
最后得到的结果是：
nextval数组
想要求解KMP算法优化后求解的nextval数组，需要以前面的next数组为基础
- 第一步：j=1时，nextval[j]=next[1]=0
- 第二步：记住一个公式
j > 1 时 { 若 P j ≠ P n e x t [ j ] ，则 n e x t v a l [ j ] = n e x t [ j ] 若 P j = P n e x t [ j ] ，则 n e x t v a l [ j ] = n e x t v a l [ n e x t [ j ] ] j>1时\begin{cases} 若P_j≠P_{next[j]}，则nextval[j]=next[j]\\ 若P_j=P_{next[j]}，则nextval[j]=nextval[next[j]]\\ \end{cases} j>1时{若Pj=Pnext[j]，则nextval[j]=next[j]若Pj=Pnext[j]，则nextval[j]=nextval[next[j]]
其中 P j P_j Pj是第 j 个字符
实操一下
以前面已求出来next数组的为例
当j=2时， P 2 P_2 P2= b , P n e x t [ 2 ] = P 1 = a P_{next[2]}=P_{1}=a Pnext[2]=P1=a,它们不相等，所以nextval[2]=next[2]=1
…
当j=6时， P 6 = a , P n e x t [ 6 ] = P 4 = b P_6=a , P_{next[6]}=P_{4}=b P6=a,Pnext[6]=P4=b,它们不相等，所以nextval[6]=next[6]=4
…
最后的结果如下：
over~
后续有需要的话再补充