考研笔记

速查：KMP 的 next 与 nextval（双口径对照）

速查表：两个教材例的逐项验算。部分匹配值法、比较次数的数法与 3 道真题见 4.2.2~4.2.3 KMP 算法及其优化；真题解析的下标口径（2015、2019、2024 均按从 0 起）也在那一页的口径差异框里。 这一页是「算竞口径 vs 教材口径」差异最大的一处——写惯 fail[0]=-1 的人，手算题会全错。

口径差异（先看这一条）

算法竞赛常见写法王道 / 408
下标起点字符串下标从 0 开始从 1 开始
数组名fail[] / pmt[] / nxt[]next[]
首项fail[0] = -1next[1] = 0
第二项fail[1] = 0next[2] = 1
含义最长相等前后缀的长度失配时跳到的位置（= 长度 + 1）
优化版通常直接写进 fail 里单独命名为 nextval

换算关系：王道的算竞的。

手算题按算竞口径写，每一项都会小 1，整张表作废。

next 数组

定义（教材原文）：

next[j] 的含义是当模式串的第 个字符失配时，跳到 next[j] 位置继续比较。

两个固定值（教材加注强调）：

「注，模式串的 next[1]=0、next[2]=1 都是固定不变的。」

对 ：（ 的最长相等前后缀长度）。

手算方法（教材给的画法）

在不匹配的位置前画一条分界线，模式串一步一步往后退，直到分界线之前能对上（首尾重合），或模式串完全跨过分界线为止。

右滑位数 已匹配的字符数 对应的部分匹配值。

教材例：模式串 'abcac'

12345
模式串abcac
next[j]01112
  • ：固定 next[1]=0，指针 和 同时加 1（模式串右滑 1 位）。
  • ：固定 next[2]=1，下次比较位置为 1，相当于向右滑动 1 位。
  • ：'ab' 无相等前后缀 → next[3]=1，右滑 2 位。
  • ：'abc' 无相等前后缀 → next[4]=1，右滑 3 位。
  • ：'abca' 最长相等前后缀是 'a'（长度 1）→ next[5]=2。

KMP 匹配算法

与 next 数组的求解相比，KMP 的匹配算法相对要简单很多，它在形式上与简单的模式匹配算法很相似。不同之处仅在于当匹配过程产生失配时，指针 不变，指针 退回到 next[j] 的位置并重新进行比较；且当指针 为 0 时，指针 和 同时加 1。也就是说，若主串的第 个位置和模式串的第 1 个字符不等，则应从主串的第 个位置开始匹配。

int Index_KMP(SString S, SString T, int next[]){
    int i = 1, j = 1;
    while(i <= S.length && j <= T.length){
        if(j == 0 || S.ch[i] == T.ch[j]){
            ++i; ++j;                 //继续比较后继字符
        }
        else
            j = next[j];              //模式串向右滑动
    }
    if(j > T.length)
        return i - T.length;          //匹配成功
    else
        return 0;
}

复杂度与适用性（教材原话）：

尽管普通模式匹配的时间复杂度是 ，KMP 算法的时间复杂度是 ，但在一般情况下，普通模式匹配的实际执行时间复杂度近似为 ，因此至今仍被采用。 KMP 算法仅在主串与子串有很多「部分匹配」时才显得比普通算法快，其主要优点是主串不回溯。

nextval 数组（4.2.3 进一步优化）

问题：前面定义的 next 数组在某些情况下尚有缺陷。

问题在于不应该出现 。理由是：当 时，下次匹配必然是 跟 比较，若 ，则相当于拿一个和 相等的字符跟 比较，这必然导致继续失配，这样的比较毫无意义。

修正规则：

若出现 ，则需要再次递归，将 next[j] 修正为 next[next[j]]，直至两者不相等为止，更新后的数组命名为 nextval。此时匹配算法不变。

可以直接修正：

教材例：模式串 'aaaab'（图 4.5）

12345
模式串aaaab
next[j]01234
nextval[j]00004

逐项验算：

相等？nextval[j]
1a——0（固定）
2a a是
3a a是
4a a是
5b a否

教材对这个例子的分析：当 、 时， 跟 （ba）失配，若用之前的 next 数组，则还需要进行 与 、 与 、 与 这 3 次比较。事实上，因为 a、 a、 a，显然后面 3 次用一个和 相同的字符跟 比较毫无意义，必然失败。

手算模板

求 next：

  1. next[1]=0，next[2]=1，直接写死。
  2. 对 ：看 的最长相等前后缀（真前缀 = 真后缀），长度 就是 next[j]。
  3. 验算：next[j] 的取值范围是 ，且相邻两项最多增 1（next[j+1] ≤ next[j]+1）。

求 nextval：

  1. 先把 next 求完整。
  2. 从 开始逐个看：比较 与 。
    • 不等 → nextval[j] = next[j]。
    • 相等 → nextval[j] = nextval[next[j]]（因为是从左往右算的，nextval[next[j]] 已经求好了）。
  3. nextval[1] 恒为 0。

记忆抓手：next 看前后缀，nextval 看字符是否重复。

高频边界

说法判断说明
「next[1]=-1」❌王道口径是 next[1]=0
「next[2] 要算」❌固定为 1
「next[j] 是最长相等前后缀的长度」❌是长度 ，即失配时跳到的位置
「KMP 的时间复杂度总是优于朴素算法」⚠️教材：普通模式匹配的实际执行时间近似 ，至今仍被采用；KMP 仅在「部分匹配」多时显快
「KMP 的主要优点是快」❌教材原话：「其主要优点是主串不回溯」
「nextval 会改变匹配算法」❌匹配算法不变，只换数组
「nextval[j] 一定小于 next[j]」❌相等时不变（ 的情形）
「求 nextval 要重新递推前后缀」❌基于已求好的 next，只比较字符
「失配时主串指针 要回退」❌ 不变； 退回 next[j]
「 时只有 加 1」❌ 和 同时加 1

链接

反向链接