对应章节：串 → KMP算法
目标：快速做next数组、匹配过程、nextval判断题。

1. 求next数组，先别背公式

核心只看：

当前字符之前的模式串中，最长相等前后缀有多长。

例如模式串：

ABABA

最长相等前后缀：

ABA

长度：

3

这就是KMP跳转依据。

2. 为什么不同教材next下标可能不一样

这是KMP最容易把人搞乱的地方。

有的教材：

下标从0开始
next[0]=-1

有的教材：

下标从1开始
next[1]=0

所以做题第一步不是直接套你背的数组，而是：

先确认题目采用哪一种next定义。

同一模式串，不同定义下的数字可能整体错一位。

3. next数组怎么理解

可以直接理解成：

第j个字符失配
↓
退到next[j]位置继续比较

本质还是：

利用前面已经匹配部分的最长相等前后缀

4. nextval为什么出现

普通next有一个低效情况。

如果失配后跳到的位置：

模式串字符和刚刚失配的字符相同

那肯定会立刻再失配一次。

所以nextval的思想：

如果跳过去还是相同字符，就继续往前跳。

5. next和nextval的区别

简单理解：

next：
按最长相等前后缀跳

nextval：
如果跳过去还是同样字符
就继续优化跳转

所以：

nextval是对next的优化

6. 高频判断题

判断1

KMP匹配过程中主串指针不会回退

通常判：

对

判断2

next数组由主串和模式串共同决定

错。

next只由模式串决定

判断3

KMP总时间复杂度是O(n+m)

对。

7. 做匹配过程题的固定方法

看到某位置失配：

主串i
模式串j

直接：

j = next[j]

主串：

i不动

继续比较。

8. 考场秒杀口诀

求next：
找最长相等前后缀

做匹配：
主串不回退
模式串按next跳

看nextval：
避免重复失配

看复杂度：
O(n+m)

9. 最危险的两个坑

坑1：next定义混用

next[0]=-1

和：

next[1]=0

不能混着用。

坑2：把next理解成“移动几格”

next通常表示：

下一次比较的位置

不是简单的：

向左移动多少格

10. 一句话总结

KMP做题最重要的不是死背next数组，而是先看题目的next定义，再用“最长相等前后缀”理解跳转；nextval只是避免无意义的重复失配。