前言
在学习串这一章节时，只有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;…
- 剩下的推理方式相同
最后得到的结果是：
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
注意：在题目中的next数组是否整体-1要根据题意判断，如果串的坐标从0开始的就要-1，没说就都算对，上面的结果是串的坐标从1开始
nextval数组
想要求解KMP算法优化后求解的nextval数组，需要以前面的next数组为基础
- 第一步：j=1时，nextval[j]=next[1]=0
- 第二步：记住一个公式
j>1时{若Pj=Pnext[j]，则nextval[j]=next[j]若Pj=Pnext[j]，则nextval[j]=nextval[next[j]]
其中Pj是第 j 个字符
实操一下
以前面已求出来next数组的为例
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
最后的结果如下：
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 | 1 | 0 | 4 |
over~
后续有需要的话再补充
