说到 KMP，很多备考数据结构统考的考生都能把那张“手算 next / nextval 的方法”背下来：什么最长相等前后缀加一、什么字符相同就往前跳。可一旦真拿到一道题，问“此时模式串向右滑动多少位”，不少人就卡住了。我当年也卡过，后来是拿一道真题反复推了三遍，才彻底想明白所谓“滑动距离”到底在滑什么、为什么 nextval 能比 next 滑得更远。这篇文章我就用一道很典型的统考风格真题，把这套东西从头到尾掰开揉碎讲清楚，连带你考场上的易错点一起搞定。
这道题问的是：给定模式串 (p = "abaabcac")，求它的 next 数组和 nextval 数组；并且当匹配过程中模式串第 5 个字符处发生失配时，使用 nextval 数组时模式串应向右滑动的距离是多少。乍看只是常规计算题，但它把 KMP 的两个核心概念拴在了一起：一个是数组怎么算，一个是失配后模式串到底怎么动。能把滑动距离的原理讲明白，KMP 基本就算入门了。
1. 先从真题视角看：这类题究竟在考什么
1.1 一道高度还原的统考风格真题
下面是这类题目在考卷上最常见的形态，代号和措辞我按教学场景稍作整理，但考法还原度很高：
已知模式串 (p = "abaabcac")，采用 KMP 算法进行字符串匹配，下标从 1 开始。
(1) 写出模式串的 next 数组和 nextval 数组；
(2) 若某次匹配在模式串第 5 个字符处失配，主串指针不动，使用 nextval 数组，模式串向右滑动的距离是多少？并说明为什么。
这道题把 KMP 中两个最容易被混淆的东西一起考了：你既要能算出两个数组，又要能解释数组在匹配过程中对应的是什么动作。很多同学第一问能拿分，第二问就靠蒙，因为平时只背计算口诀，没有把“j 回退到 nextval[j]”和“模式串向右滑动”联系起来。
1.2 为什么这样一道题能难住一多半人
我见过不少备考者，他们能流利地说出“nextval[j] 是 next[j] 的改进版”，但你要问他“改进”在哪里，他就说不清了。常见的错误有三种：
第一种，把 next 和 nextval 当成两个独立表，算完就完了，压根没想过它们对应的是失配后 j 要跳去的位置。于是第二问直接写“滑动 5 - 2 = 3 位”，这其实是拿 next 数组算的，不是 nextval。
第二种，知道要用 nextval，但搞不清滑动距离到底是 (j - nextval[j]) 还是 (nextval[j])。有的同学写成“向右滑动 nextval[j] 位”，也就是 1 位，方向直接反了。
第三种，对 nextval 的链式回退规则不理解，算到一半就乱套。比如计算 nextval[5] 时，明明确认了 (p[5] == p[next[5]])，却不知道下一步要取 nextval[next[5]]，而不是直接照抄 next[5]。
这道题的意义就在于：它逼你把“数组值”和“物理滑动”一一对应起来。只要能讲清为什么失配发生在第 5 个字符、为什么 nextval[5] = 1、为什么滑动距离是 4 而不是 3，那么 KMP 的核心动作你就真的拿下了。
2. 先把 next 数组的手算逻辑彻底拆干净
2.1 next 数组的定义：不是直觉上的“最长相等前后缀加一”
很多教材给出的是这个说法：对于模式串 (p[1..m])，next[j] 表示当 (p[j]) 与主串失配时，j 应该回退到的位置。具体计算时，则是看 (p[1..j-1]) 这一段字符串的最长相等前后缀长度，再加上 1。
这里有个很容易忽略的边界：next[1] 和 next[2]。按统考常用的下标从 1 开始的约定，next[1] = 0，next[2] = 1。理由很简单，当第一个字符就失配时，模式串没法再往前退了，所以用 0 作为哨兵；第二个字符失配时，前面只匹配过一个字符，而这个字符的最长相等前后缀长度是 0，所以 next[2] = 0 + 1 = 1。
为了不让大家死记口号，我建议别急着背“加一”，而是先看实际例子。以 (p = "abaabcac") 为例，我们可以先把每个位置 j 对应的“已匹配前缀”写出来：
| j | 已匹配部分 (p[1..j-1]) | 最长相等真前后缀长度 | next[j] |
|---|---|---|---|
| 1 | 空 | - | 0 |
| 2 | a | 0 | 1 |
| 3 | ab | 0 | 1 |
| 4 | aba | 1（前缀 a = 后缀 a） | 2 |
| 5 | abaa | 1（前缀 a = 后缀 a） | 2 |
| 6 | abaab | 2（前缀 ab = 后缀 ab） | 3 |
| 7 | abaabc | 0 | 1 |
| 8 | abaabca | 1（前缀 a = 后缀 a） | 2 |
所以第一问的 next 数组是：
[ next = [0, 1, 1, 2, 2, 3, 1, 2] ]
注意这里的数组元素是从下标 1 开始陈列的，实际写成序列就是 0、1、1、2、2、3、1、2。
2.2 手算时最容易出错的两个位置
位置 4 和位置 6 是这道题里最容易算错的地方，我把它们的判断逻辑单独拿出来讲。
先看位置 4。已匹配部分是 (p[1..3] = "aba")，要找的是它的最长相等真前后缀。“真前后缀”的意思是不能取整个字符串本身。对 "aba" 来说，前缀 a 和后缀 a 相等，长度是 1；前缀 ab 和后缀 ba 不相等；所以最长相等真前后缀长度就是 1，next[4] = 1 + 1 = 2。
再看位置 6。已匹配部分是 (p[1..5] = "abaab")。这里前缀 ab 等于后缀 ab，长度是 2。有些人会把前缀 aba 和后缀 aab 拿去比，结果发现不相等就慌了，其实只需要看最长的那个候选是否成立，不成立再往下缩短就行。复杂度并不高，关键是别跳步。
2.3 为什么统考爱用 "abaabcac" 这个串
这个模式串设计得很巧妙。它里面有重复出现的单字符 a，有两次字符对 ab，有中间断开的地方，几乎覆盖了 next 计算的所有典型情况。比如 j = 3 时最长相等前后缀长度为 0，j = 6 时长度为 2，j = 7 时又掉回 0。你要是能把这一串算熟练，考试里遇到类似的模式串基本就不会再犯原则性错误。
而且这个串也方便我们后面讲 nextval。因为它并不是连续重复字符那种看一眼就懂的极端模式，而是穿插了不同字符的“正常模式”，反而更能考察你对规则的理解，而不是对对称性的直觉。
3. nextval 的真面目：把已知会失败的比较提前消灭
3.1 nextval 的递推规则，一句话说清
nextval 的递推规则是：
[ nextval[1] = 0 ]
对于 (j \ge 2)，先看 (p[j]) 和 (p[next[j]]) 是否相等：
- 若不相等，(nextval[j] = next[j])；
- 若相等，(nextval[j] = nextval[next[j]])。
很多同学背错了后半句，以为相等时 nextval 就等于 nextval[j-1]，这是大错特错。正确做法是：(j) 要回溯到 (next[j]) 那个位置，再看那个位置的 nextval 值。
为什么这么定义？因为 next[j] 指示的是失配后 j 要去的位置，但如果 (p[j]) 恰好和 (p[next[j]]) 是同一个字符，那么就算你跳过去了，下一次比较拿同一个字符去对主串里那个已经失配的字符，结果仍然是失配。与其做一次注定失败的比较，不如继续顺着 nextval 跳到更前面，跳过这次无效劳动。
这正是 nextval 的核心思想：它不是在改写 next 数组，而是在回收“已经能确定会失败”的比较机会。
3.2 逐位演算 "abaabcac" 的 nextval
我从头到尾算一遍，大家对着表看：
| j | p[j] | next[j] | p[next[j]] | 是否相等 | nextval[j] |
|---|---|---|---|---|---|
| 1 | a | 0 | - | - | 0 |
| 2 | b | 1 | a | 否 | 1 |
| 3 | a | 1 | a | 是 | nextval[1] = 0 |
| 4 | a | 2 | b | 否 | 2 |
| 5 | b | 2 | b | 是 | nextval[2] = 1 |
| 6 | c | 3 | a | 否 | 3 |
| 7 | a | 1 | a | 是 | nextval[1] = 0 |
| 8 | c | 2 | b | 否 | 2 |
因此：
[ nextval = [0, 1, 0, 2, 1, 3, 0, 2] ]
细心的同学会发现，位置 4 和位置 5 的运转逻辑特别能说明问题。位置 4 中 (p[4] = a)，而 (p[next[4]] = p[2] = b)，字符不同，所以 nextval[4] 直接采用 next[4] = 2。而位置 5 中 (p[5] = b)，(p[next[5]] = p[2] = b)，字符相同，所以不能停在 next[5] = 2 这里，而是继续跳到 nextval[2] = 1，最终 nextval[5] = 1。
3.3 链式回退是 nextval 计算中的隐形陷阱
实际手算时，最阴险的坑就是链式回退不是一次就结束的。比如某个位置 (p[j]) 与 (p[next[j]]) 相等，你跳到 nextval[next[j]]，发现那里的字符仍然有可能继续满足相等条件，这时候得继续往前跳吗？
答案是：不需要你手工一层层展开到最底层。因为 nextval 数组是按 j 从小到大的顺序计算的，(nextval[next[j]]) 这个值在你算到 (j) 之前就已经是最终定稿的版本了，它内部已经包含了多级跳转的压缩。比如上面位置 5 用到 nextval[2] = 1，而 nextval[2] 本身就是从 next[2] = 1 再判断后得到的，它已经是最终结果，不会再继续跳。
这个性质给手算带来了很大方便：你只需要判断一层相等关系，然后直接查表引用之前算好的 nextval 值即可。
3.4 nextval 为什么可能比 next 更小
从数值上看，nextval[j] 通常不等于 next[j]，而且往往是更小的值，甚至可能变成 0。有人会疑惑：nextval 既然是“优化”，为什么数值还变小了？
别忘了，数组值是描述“失配后跳回的位置”。值越小，说明模式串回退得越狠，对应到物理动作上，就是模式串整体向右滑动的距离越大。所以 nextval[j] 更小并不代表退化，恰恰代表优化——它把那些无谓的重复比较跳过去了。
至此，我们还剩一个关键问题：滑动距离到底怎么从数组值换算出来，我放到下一节专门讲。
4. 滑动距离的本质：主串指针不动，模式串靠什么找回进度
4.1 从“j 回退”到“模式串右移”的等价换算
KMP 的标准执行流程是：匹配到 (i) 位置和 (j) 位置时若失配，主串指针 (i) 不动，模式串指针 (j) 回退为 (next[j])（或 (nextval[j])）。但考题如果问“模式串向右滑动多少位”，它问的其实是另一个等价量。
要知道，主串当前位置 (i) 与模式串当前比较位置 (j) 是对齐的。失配后 (j) 变成了 (new_j)，那么原本 (p[j]) 所占的那个主串位置，就轮到 (p[new_j]) 来对齐。从模式串整体来看，相当于模式串向右移动了 (j - new_j) 个位置。
所以：
- 用 next 数组时，滑动距离是 (j - next[j])；
- 用 nextval 数组时，滑动距离是 (j - nextval[j])。
这里必须强调，滑动距离不是 next[j]，也不是 nextval[j]，而是两者之间的差。这个点几乎年年有人错。
4.2 回到真题：第 5 个字符失配，nextval 为什么能滑 4 位
现在我们把第 5 个字符失配的场景完整演一遍。
设某次匹配时，主串中已成功匹配了前 4 个字符 (p[1..4] = "abaa")，而第 5 个字符处，主串对应的字符（我们记为 (\alpha)）不等于模式串的 (p[5] = 'b')。换句话说，失配点是主串第 (i) 个位置、模式串第 5 个位置。
如果只考虑 next 数组，next[5] = 2，那么 j 回退到 2，滑动距离是 5 - 2 = 3。可我们已知第 5 个位置主串字符 (\alpha) 不是 b。而模式串第 2 个字符恰恰也是 b，所以 j 回退到 2 之后，拿 (p[2] = 'b') 去和 (\alpha) 比较，结果必然是再次失配。既然这一趟注定白比较，还不如直接利用 nextval 把它跳掉。
nextval[5] = 1，所以使用 nextval 数组时，j 直接回退到 1，滑动距离是 5 - 1 = 4。模式串一下多滑了 1 位，跳过了拿 b 再比一次的无用功。在考试里，第二问的答案写“滑动距离 4 位”还不够，最好补一句：因为 nextval[5] = 1，且失配后主串指针不动，模式串向右移动 5 - 1 = 4 位。
4.3 极端例子：连续重复字符下，一次滑动能从 1 变成 5
只看 "abaabcac" 这个例子，nextval 带来的滑动优势感还不够直观。我再给一个更极端的模式串：(p = "aaaaab")，长度 6。
手算它的 next：
| j | p[1..j-1] | next[j] |
|---|---|---|
| 1 | - | 0 |
| 2 | a | 1 |
| 3 | aa | 2 |
| 4 | aaa | 3 |
| 5 | aaaa | 4 |
| 6 | aaaaa | 5 |
再算 nextval：由于 (p[2], p[3], p[4], p[5]) 都等于前缀 a，而 next[2..5] 指向的也都是 a，所以这几位会一路链回：
[ nextval = [0, 0, 0, 0, 0, 5] ]
这时候，假如失配发生在模式串第 5 个字符处，用 next 数组只滑 5 - 4 = 1 位；而用 nextval 数组直接滑 5 - 0 = 5 位。
在实际匹配中，比如主串是 "...aaaac..."，模式串滑 1 位后，(p[4] = 'a') 对上的仍是那个 c，还要再确认一次失配，然后接着滑 1 位，再确认一次……等于连续做 4 次注定失败的比较。而 nextval 一步把模式串整段滑过去，让 (p[1] = 'a') 直接对接失配字符。省掉的不是 1 次比较，而是一整段无效比较。
4.4 为什么说滑动距离的本质是“安全跳过量”
如果把暴力匹配比作逐格试探，KMP 每次失配后的滑动距离，就是模式串整体向右挪动的格子数。这个格子数不是越大越好，而是要在“绝对不遗漏可能的匹配起点”的前提下尽量大。
(next[j]) 给出的安全跳过量，基于已匹配前缀的自重叠关系；(nextval[j]) 则在它的基础上进一步排除了“就算跳过去也会立刻失配”的情况，所以安全跳过量进一步增大。这就是为什么 nextval 数组能在时间上继续优化 KMP——它让模式串更敢大步往前走。
5. 考场实战：这类题的易错点与验算方法
5.1 下标从 1 还是从 0 开始，先看题再动手
统考数据结构教材里字符串通常从下标 1 开始，next[1] = 0、next[2] = 1。但有些习题或自命题会采用下标从 0 开始，此时 next 数组的初值和递推写法都会变，常见定义变成 next[0] = -1，next[1] = 0 之类。同一个模式串，两套体系算出的数组序列完全不同，不要混用。
我的建议是：拿到题先看有没有给出“下标从 1 开始”的说明。如果有，就按本文这套规则；如果没说明，默认按你平时教材的习惯走。写答案时最好顺手标一句“以下按字符串下标从 1 开始计”，既提醒自己，也能让阅卷时印象分好一点。
5.2 nextval 的链式引用怪圈：算到一半发现引用还没算
按 j 从小到大递推 nextval 时，有一个细节容易让人怀疑自己算错：当 (p[j] = p[next[j]]) 时，要引用 (nextval[next[j]])，而这个 nextval 值往往已经在前面算好了。因为 next[j] 一定小于 j，所以这个引用总是安全的，不会出现“引用了一个尚未计算的值”的尴尬。
这背后其实是一种动态规划思想：后一个位置的优化结果依赖于前面位置已经计算好的优化结果。你不需要每次从头推导，查表就行。一旦理解了这个顺序性，手算速度能快不少。
5.3 答题时最容易扣分的两种措辞
第一，当题目明确问“使用 nextval 数组”时，滑动距离必须写 (j - nextval[j])。有些同学心里算对了，但写成“滑动 nextval[j] 位”，这就等于直接把数组值当成滑动量，会扣分。
第二，如果你用了 next 和 nextval 两套数组分别算滑动距离，一定要分清楚不同失配位置对应不同结果。同样是模式串 "abaabcac"，第 5 位失配滑 4 位，第 6 位失配呢？(nextval[6] = 3)，滑动距离就是 6 - 3 = 3。第 7 位失配呢？(nextval[7] = 0)，滑动距离 7 位。可见答案因失配位置而变，不能笼统说“这个模式串滑 N 位”。
5.4 一个超实用的验算方法：随手拉一条主串草稿
备考时，我建议你做完这类题后，不要直接看答案，而是自己写一条主串，把匹配过程一步步画出来。以真题第二问为例，你可以假设主串的失配位置字符为某个非 b 字符，然后模拟：
- 用 next：j 先跳到 2，拿 b 去比，再失配，j 再跳，整体多比了一次；
- 用 nextval：j 直接到 1，少了一次无效比较。
画完这遍草稿，你会深刻理解“滑动距离”不是抽象公式，而是模式串在文本上的实际位移。这个方法在考场上可能没时间完整做，但平时练习的时候做上三五个，考试基本不会再错。
我个人备考时的体会是：KMP 难不在公式，难在把数组值、指针回退和模式串位移这三层概念扭到一起。只要你肯动手，拿任意一个模式串，算完 next 和 nextval，再拉一条主串把失配过程画一遍，最多三道题就能彻底打通。记住这句话：nextval 不是为了让数组更小，而是为了让模式串在失配后，能理直气壮地跨过那些一定走不通的路。
