KMP 算法

2026 大纲 六（八）字符串模式匹配 的主篇（先读《BF 算法》，本篇直接接在它的结论上）。

KMP 只改了 BF 的一行

BF 的失败方式很具体：失配的一瞬间，j = 1，本趟辛辛苦苦比对上的 $j-1$ 个字符全部作废，i 也退回本趟起点的下一位重来。

但那 $j-1$ 个字符并不是白比的——它们等于模式串的前缀 $T_1\cdots T_{j-1}$，这是一个与主串无关的已知量。既然已知，"下一个可能成功的对齐位置在哪"就能提前算出来。KMP 做的就是这件事：拿模式串自己算一张表（next 数组），失配时不再从头开始，而是查表决定 $j$ 退到哪儿；$i$ 一步都不退。

落到代码上，KMP 与 BF 只差两处：

// BF：  else { i = i - j + 2;  j = 1; }
// KMP： else {                 j = next[j]; }

i 从 else 分支里彻底消失了——这就是"主串指针不回溯"的全部实现。剩下的所有内容，都是在回答两个问题：next 表里该填什么，以及它怎么算出来。

滑动距离为什么只由模式串决定

这是 KMP 唯一需要真正想明白的地方，想通了 next 的定义就是顺出来的。

设本趟比到 $S_i$ 与 $T_j$ 时失配（$j>1$）。此刻我们确切知道：

$$T_1{T}_2\cdots T_{j-1}=S_{i-j+1}{S}_{i-j+2}\cdots S_{i-1}$$

现在把问题精确地提出来：$i$ 保持不动，模式串该向右滑到哪儿，使 $S_i$ 接着与模式串的第 $k$ 个字符比较？ 要让这次滑动不漏掉任何可能的匹配，滑过去之后模式串的前 $k-1$ 个字符必须与 $S_i$ 之前那 $k-1$ 个字符对上：

$$\begin{array}{}\text{(1)}& T_1{T}_2\cdots T_{k-1}=S_{i-k+1}\cdots S_{i-1}\end{array}$$

而由已知的部分匹配结果，$S_{i-k+1}\cdots S_{i-1}$ 正是 $T_{j-k+1}\cdots T_{j-1}$——它们都是那 $j-1$ 个已匹配字符的后 $k-1$ 个。代入 (1)：

$$\begin{array}{}\text{(2)}& \boxed{{\displaystyle T_1{T}_2\cdots T_{k-1}=T_{j-k+1}\cdots T_{j-1}}}\end{array}$$

式 (2) 里已经没有主串了。 它只对模式串提要求：$T_1\cdots T_{j-1}$ 这一段里，长度为 $k-1$ 的前缀与后缀必须相等。

这就是全部魔法的来源。滑动距离只由模式串自身决定，可以在还没看到主串的时候一次性算好；而为了不漏解又滑得尽量远，$k$ 取满足式 (2) 的最大值。

那个 +1 从哪来。 令 $\ell$ 为最长相等前后缀的长度，则

$$\text{next}[j]=\ell +1$$

$\ell$ 是长度，$\text{next}[j]$ 是位置，两者性质不同。推理只有一步：滑动到位后，模式串的前 $\ell$ 个字符已经与主串中 $S_i$ 之前的 $\ell$ 个字符对齐且相等（式 (2) 保证），不需要再比一次；位置 $1\sim \ell$ 既然都免了，下一个要与 $S_i$ 比的就是位置 $\ell +1$。

而"长度为 $\ell$ 的前缀恰好占据位置 $1\sim \ell$"这件事，成立的前提是位置从 1 开始编号。换成 0 起点，前缀占下标 $0\sim \ell -1$，下一个下标就是 $\ell$ 本身，数组里直接存长度、+1 随之消失——下一节那两种口径的差异，唯一来源就在这里。

最后是哨兵。 $j=1$ 时模式串内部没有任何信息可用（前面一个字符都没有），规定 $\text{next}[1]=0$，含义是"退无可退"：此时执行 i++, j++，相当于模式串整体右移一位、从头再比。这一步不算一次字符比较——数比较次数的题会用到。另外由定义可直接得出恒等式 $\text{next}[2]\equiv 1$。

先看一眼

下面的可视化把 next 表和匹配过程并排画了出来。看的时候盯住两件事：失配时 $i$ 有没有动，以及$j$ 退到的那一格与模式串前缀的对应关系。

加载可视化中...

看完你应该确认：$i$ 的取值序列是单调不减的，主串每个字符只被扫过一遍。

两种 next 口径怎么认（做题前必须先分清）

同一个模式串，不同教材给出的 next 表可以整体差 1，甚至下标范围都不同。 这不是谁对谁错，是两套编号约定。而 408 真题两套都出现过，所以做题第一步是先认口径。

	位置口径（本文，1 起点）	长度口径（0 起点）
下标范围与哨兵	$T[1..m]$（$T[0]$ 闲置），$\text{next}[1]=0$	$T[0..m-1]$，$\text{next}[0]=-1$
存的是什么	失配后该比第几个字符（位置）	最长相等前后缀的长度（0 起点下也正是下一个下标）
失配时怎么写	j = next[j]；j == 0 时 i++, j++	j = next[j]；j == -1 时 i++, j++
$T=\text{"abaabcac"}$	0 1 1 2 2 3 1 2	−1 0 0 1 1 2 0 1
换算	—	${\text{next}}_0[j]={\text{next}}_1[j+1]-1$

怎么判，按可靠性排序：

① 题面给了定义式或填好的部分表格，一律照题面。 这是最可靠的依据——真题会在题干里写清楚"约定 next[j] = ……"。

② 看首两项。 位置口径是 0、1；长度口径首项是 $-1$。若首两项是 0、0，那既不是 next 也不是 nextval，而是部分匹配表 PM——它存 $T_1\cdots T_j$（注意含第 $j$ 位）的最长相等前后缀长度、不加 1，"abaabcac" 对应 0 0 1 1 2 0 1 0，换算关系是 ${\text{next}}_1[j]=\text{pm}[j-1]+1$。

③ 看代码里的哨兵。 j == 0 是位置口径，j == -1 是长度口径。

本文与站内可视化统一采用位置口径（与严蔚敏教材一致）。认错口径会让整张表错位一格，后面全错。

手工求 next：一个 $j$ 一行，三处容易错

手工求法就一句口诀：看第 $j$ 个字符前面那一段，找最长的"头尾相同段"，长度加 1。

具体到每个 $j$（从 1 到 $m$）：写出 $T_1\cdots T_{j-1}$ → 找它的最长相等前后缀（前缀、后缀都不能是整串）→ 记长度为 $\ell$ → $\text{next}[j]=\ell +1$。特别地 $\text{next}[1]=0$。

以 $T=\text{"abaabcac"}$ 为例：

$j$	$T_j$	$T_1\cdots T_{j-1}$	最长相等前后缀	$\ell$	$\text{next}[j]=\ell +1$
1	a	（空）	—	—	0（规定）
2	b	"a"	无	0	1
3	a	"ab"	无	0	1
4	a	"aba"	"a"	1	2
5	b	"abaa"	"a"	1	2
6	c	"abaab"	"ab"	2	3
7	a	"abaabc"	无	0	1
8	c	"abaabca"	"a"	1	2

三处容易做错的地方，都在这张表里：

• 第 5 行："abaa" 的相等前后缀是 "a" 而不是 "aa"——后缀确实是 "aa"，但长度 2 的前缀是 $T_1{T}_2=\text{"ab"}$，不是 "aa"。前缀必须从第 1 个字符起连续取，不能挑着取。
• 第 6 行："abaab" 要取 "ab"（$\ell =2$）而不是 "a"（$\ell =1$）——要最长的。
• 第 7 行："abaabc" 以 c 结尾、以 a 开头，连长度 1 的相等前后缀都没有，$\ell =0$，$\text{next}[7]=1$。

next 的形式化定义式（想看严格表述时展开）

$$\text{next}[j]=\{\begin{array}{ll}0,& j=1\\ max\{k\mid 1<k<j,T_1\cdots T_{k-1}=T_{j-k+1}\cdots T_{j-1}\},& \text{该集合非空}\\ 1,& \text{其他情况}\end{array}$$

三行分别对应三种处境：$j=1$ 时模式串内部已无信息可用，规定为哨兵 0；中间那行是存在非空相等前后缀时取最大的 $k$；第三行指 $T_1\cdots T_{j-1}$ 没有任何非空相等前后缀，模式串只能整体挪到与 $S_i$ 对齐、从第 1 个字符重比。

代码：两段，结构一模一样

// 求 next 数组（串下标从 1 开始，T[0] 闲置不用）
void getNext(char T[], int next[], int m) {
    int j = 1, k = 0;     // j 走的是 T 自己（当主串），k 是模式串指针
    next[1] = 0;          // 哨兵
    while (j < m) {       // 只算到 next[m]，写成 j <= m 会越界
        if (k == 0 || T[j] == T[k]) {
            j++; k++;
            next[j] = k;  // 赋的是新 j、新 k：长度 k-1 → 位置 k，即"ℓ+1"
        } else {
            k = next[k];  // 扩展不下去，退到次长的相等前后缀继续试
        }
    }
}

// KMP 匹配；返回首次出现的起始位置，失败返回 0
int KMP(char S[], char T[], int next[], int n, int m) {
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (j == 0 || S[i] == T[j]) {
            i++; j++;             // 主串指针只会前进，从不回退
        } else {
            j = next[j];          // 失配：i 不动，模式串右滑到 next[j]
        }
    }
    return (j > m) ? i - m : 0;   // i 停在匹配段之后一位
}

j == 0 必须写在 || 的左边：短路求值保证这时不去访问闲置的 T[0]。

把两段并排看，会发现求 next 就是"模式串对自身做一次 KMP"——$j$ 扮演主串指针（永不后退），$k$ 扮演模式串指针（失配就 k = next[k] 回退）：

	KMP 匹配	求 next
谁在往前走（永不后退）	主串指针 $i$	模式串指针 $j$
谁在回退	模式串指针 $j$	辅助指针 $k$
比较的两个字符	$S_i$ 与 $T_j$	$T_j$ 与 $T_k$
相等时	$i++,j++$	$j++,k++$，并记下 $\text{next}[j]=k$
不等时	$j\leftarrow \text{next}[j]$	$k\leftarrow \text{next}[k]$
退到 0 时	$i++,j++$（模式串右移一位）	$j++,k++$（$\text{next}[j]=1$）

代码里之所以不能对每个 $j$ 都从头找一遍前后缀（那样是 $O(m^2)$），靠的正是 k = next[k] 这条递推：$T_1\cdots T_{j-1}$ 的所有相等前后缀里，比当前长度短的那些，恰好就是 $T_1\cdots T_{k-1}$ 的相等前后缀——所以"找次长的"等于"到 $\text{next}[k]$ 去取"。

递推的正确性证明与 getNext 逐步执行（想彻底弄懂求 next 的代码就展开）

已知 $\text{next}[j]=k$，即 $T_1\cdots T_{k-1}=T_{j-k+1}\cdots T_{j-1}$，且 $k-1$ 是最长的。

情形 A：$T_j=T_k$。 把等式两边各接上一个字符（左接 $T_k$、右接 $T_j$，二者相等）：

$$T_1\cdots T_{k-1}{T}_k=T_{j-k+1}\cdots T_{j-1}{T}_j$$

相等前后缀的长度从 $k-1$ 变成 $k$，所以 $\text{next}[j+1]=k+1=\text{next}[j]+1$。

情形 B：$T_j\ne T_k$。 长度 $k-1$ 的前后缀扩展不下去了，只能找次长的再试。

关键结论：$T_1\cdots T_{j-1}$ 的所有相等前后缀里，比 $k-1$ 短的那些，恰好就是 $T_1\cdots T_{k-1}$ 的相等前后缀。

证明只要一行：设长度 $\ell <k-1$ 的前后缀相等，即 $T_1\cdots T_{\ell }$ 等于 $T_1\cdots T_{j-1}$ 的长度为 $\ell$ 的后缀。而 $T_1\cdots T_{j-1}$ 的长度为 $\ell$ 的后缀，同时也是 $T_{j-k+1}\cdots T_{j-1}$ 的长度为 $\ell$ 的后缀（因为 $\ell <k-1$，落在这一段里面）；由 $T_1\cdots T_{k-1}=T_{j-k+1}\cdots T_{j-1}$，它又等于 $T_1\cdots T_{k-1}$ 的长度为 $\ell$ 的后缀。所以 $\ell$ 是 $T_1\cdots T_{k-1}$ 的相等前后缀长度。反向同理。

于是次长相等前后缀的长度 $=\text{next}[k]-1$，对应位置就是 $\text{next}[k]$，故 $k\leftarrow \text{next}[k]$ 后回到情形 A/B 重新判断，一直退到 $T_j=T_k$，或退到 $k=0$（此时 $\text{next}[j+1]=1$）。因为 $k=\text{next}[j]<j$，$\text{next}[k]$ 在更早的迭代里已经算好，递推没有循环依赖。

getNext 在 $T=\text{"abaabcac"}$ 上的逐步执行（— 表示该次迭代没有写入 next）：

迭代	进入时 $j,k$	判断	动作	写入
1	1, 0	$k=0$	$j=2,k=1$	$\text{next}[2]=1$
2	2, 1	$T_2=b\ne T_1=a$	$k=\text{next}[1]=0$	—
3	2, 0	$k=0$	$j=3,k=1$	$\text{next}[3]=1$
4	3, 1	$T_3=a=T_1=a$	$j=4,k=2$	$\text{next}[4]=2$
5	4, 2	$T_4=a\ne T_2=b$	$k=\text{next}[2]=1$	—
6	4, 1	$T_4=a=T_1=a$	$j=5,k=2$	$\text{next}[5]=2$
7	5, 2	$T_5=b=T_2=b$	$j=6,k=3$	$\text{next}[6]=3$
8	6, 3	$T_6=c\ne T_3=a$	$k=\text{next}[3]=1$	—
9	6, 1	$T_6=c\ne T_1=a$	$k=\text{next}[1]=0$	—
10	6, 0	$k=0$	$j=7,k=1$	$\text{next}[7]=1$
11	7, 1	$T_7=a=T_1=a$	$j=8,k=2$	$\text{next}[8]=2$
—	8, 2	$j<m$ 不成立	退出	—

结果 $0,1,1,2,2,3,1,2$，与手工求解表逐格一致。迭代 8→9 连退两次，正是情形 B 的递归回退在起作用。

走一遍匹配：数清楚哪些算比较

以 $S=\text{"ababcabcac"}$、$T=\text{"abcac"}$ 为例。先求 $T$ 的 next：$T_1\cdots T_{j-1}$ 依次是空、"a"、"ab"、"abc"、"abca"，最长相等前后缀长度为 —、0、0、0、1，故

$$\text{next}[]=0,1,1,1,2$$

匹配过程：

步	$i$	$j$	$S_i$ vs $T_j$	动作
1	1	1	$a=a$	$i=2,j=2$
2	2	2	$b=b$	$i=3,j=3$
3	3	3	$a\ne c$	$j\leftarrow \text{next}[3]=1$，$i$ 不动
4	3	1	$a=a$	$i=4,j=2$
5	4	2	$b=b$	$i=5,j=3$
6	5	3	$c=c$	$i=6,j=4$
7	6	4	$a=a$	$i=7,j=5$
8	7	5	$b\ne c$	$j\leftarrow \text{next}[5]=2$，$i$ 不动
9	7	2	$b=b$	$i=8,j=3$
10	8	3	$c=c$	$i=9,j=4$
11	9	4	$a=a$	$i=10,j=5$
12	10	5	$c=c$	$i=11,j=6>m$，成功，返回 $11-5=6$

这张表的每一行都算一次字符比较，共 12 次，同一组输入 BF 需要 16 次。数比较次数的题就照这个格式列表，两条规矩要认准：

• 失配的那一次也算一次比较（第 3 步、第 8 步）——"$S_3=a$ 与 $T_3=c$"是真真切切比过的，不能因为结果是"不等"就漏掉；
• $j\leftarrow \text{next}[j]$ 是查表跳转，不算比较——回退本身不产生字符比较，回退之后在新位置上的那一次才算（第 4 步、第 9 步）。

比 BF 少的那 4 次不是重点。真正的差别是两处结构性事实：$i$ 的取值序列 $1,2,3,3,4,5,6,7,7,8,9,10$ 单调不减；第 8 步一次滑动就跳过了 BF 里第 4、5 两趟注定失败的对齐位置。

为什么是 $O(n+m)$：只讲"$i$ 不回退"是半个证明

"主串指针不回溯"只说明 $i$ 最多前进 $n$ 步，没有排除另一种坏情况：$i$ 不动，而 $j$ 一路 next 回退很多次。要真的证出 $O(n)$，必须把两类步数一起数。

每次循环迭代恰好落进两个分支之一：

分支	对 $i$ 的影响	对 $j$ 的影响
前进分支（$j=0$ 或 $S_i=T_j$）	$i+=1$	$j+=1$
回退分支（失配）	不变	$j\leftarrow \text{next}[j]$，因 $\text{next}[j]<j$，故 $j$ 至少减 1

四步就数完：

1. 前进分支次数 $\le n$：$i$ 从 1 出发、单调递增，循环条件要求 $i\le n$。
2. $j$ 的增量总和 $\le$ 前进分支次数 $\le n$：$j$ 只在前进分支加 1。
3. $j$ 的减量总和 $\le$ 增量总和 $+j$ 的初值 $=n+1$：$j$ 始终非负，减掉的总量不可能超过"曾经加进去的总量加上起始值"。
4. 回退分支次数 $\le$ $j$ 的减量总和 $\le n+1$：每次回退至少减 1。

两类相加，总迭代次数 $\le 2n+1$，即匹配阶段 $O(n)$。这就是 $j$ 的回退"不会积少成多"的原因：$j$ 每退一格，之前必然有某一格是靠 $i$ 前进一步换来的。

预处理阶段的结构与匹配完全同构，把上面四条里的 $n$ 换成 $m$ 逐条成立，故求 next 是 $O(m)$。两阶段串行，合计 $O(n+m)$；空间 $O(m)$（一个长度为 $m$ 的数组，与主串长度无关），这是相对 BF 的 $O(1)$ 付出的代价。

两条常被记反的边界：① $O(n+m)$ 是最坏情形的上界，不只是平均——这正是相对 BF（最坏 $O(nm)$）的核心改进。② 但"最坏更优"不等于"平均更快"：一般文本上 BF 的实际执行时间也接近 $O(n+m)$，KMP 只在主串与模式串之间存在大量部分匹配时才明显占优。它更本质的价值是主串只需从头到尾扫一遍，可以边读入边匹配。

nextval：把注定要失败的那次比较也跳掉

next 还留了一处浪费。如果 $T_j=T_{\text{next}[j]}$，那么退到 $\text{next}[j]$ 之后必然还是失配——刚才是 $S_i\ne T_j$ 才失配的，若 $T_{\text{next}[j]}$ 与 $T_j$ 是同一个字符，比较结果只能还是不等。这次比较的结果可以预知，纯属白比。

看 $T=\text{"aaaab"}$，$\text{next}[]=0,1,2,3,4$，拿它去匹配 $S=\text{"aaabaaaab"}$：$i=4$ 时 $S_4=b$ 与 $T_4=a$ 失配，按 next 要依次退到 $j=3,2,1$ 再比三次，而 $T_3=T_2=T_1=a$，这三次的结果早就注定。走完全程：用 next 共 12 次字符比较，用 nextval 只需 9 次，恰好省掉这 3 次。

修正规则：

$$\text{nextval}[j]=\{\begin{array}{ll}\text{nextval}[\text{next}[j]],& T_j=T_{\text{next}[j]}\\ \text{next}[j],& T_j\ne T_{\text{next}[j]}\end{array}$$

并规定 $\text{nextval}[1]=0$。

相等时取的是 $\text{nextval}[\text{next}[j]]$ 而不是 $\text{next}[\text{next}[j]]$——这是最容易写错的一处。因为 $\text{next}[j]<j$，$\text{nextval}[\text{next}[j]]$ 在更早的位置上已经算好，而且它本身已经是"跳到底"的结果，一步到位。这也保证了手工求解可以从左到右一遍过，不必反复递归。

同一个 $T=\text{"abaabcac"}$，先求出 next 再逐个修正：

$j$	$T_j$	$\text{next}[j]$	$T_{\text{next}[j]}$	是否相等	$\text{nextval}[j]$
1	a	0	—	—	0（规定）
2	b	1	a	$b\ne a$	1
3	a	1	a	$a=a$	0（取 $\text{nextval}[1]$）
4	a	2	b	$a\ne b$	2
5	b	2	b	$b=b$	1（取 $\text{nextval}[2]$）
6	c	3	a	$c\ne a$	3
7	a	1	a	$a=a$	0（取 $\text{nextval}[1]$）
8	c	2	b	$c\ne b$	2

收益有多大，取决于模式串长什么样：$\text{nextval}[j]\ne \text{next}[j]$ 当且仅当 $T_j=T_{\text{next}[j]}$。"aaaab" 这种长串重复字符差别最大（$0,1,2,3,4$ 变成 $0,0,0,0,4$，回退链被一次压平）；而 "abcde" 这种各字符互不相同的，$j\ge 2$ 时 $\text{next}[j]\equiv 1$、$T_j\ne T_1$ 恒成立，修正条件永不触发，两张表完全相同。

getNextval 的代码（要写代码题时展开）

// 求 nextval 数组（串下标从 1 开始，T[0] 闲置不用）
void getNextval(char T[], int nextval[], int m) {
    int j = 1, k = 0;
    nextval[1] = 0;
    while (j < m) {
        if (k == 0 || T[j] == T[k]) {
            j++;
            k++;
            if (T[j] != T[k])
                nextval[j] = k;            // 与 next 相同：退到 k 后还有得比
            else
                nextval[j] = nextval[k];   // 退到 k 后必然再失配，直接沿用 k 的结果
        } else {
            k = nextval[k];                // 回退时也用修正后的表，收敛更快
        }
    }
}

与 getNext 的差别只有两处：写入前多一次 T[j] != T[k] 判断；回退用 nextval[k]。注意 T[j] 与 T[k] 都是 j++, k++ 之后的新值，正好对应修正规则里的 $T_j$ 与 $T_{\text{next}[j]}$。

考点速记

三条会被反复调用的结论：

1. 滑动距离只由模式串自身决定——这是 KMP 能做预处理的唯一理由；+1 只是 1 起点下"长度 → 位置"的换算，换成 0 起点就没有了。
2. $O(n+m)$ 的一半来自"$i$ 不回退"，另一半来自"$j$ 的回退总量不超过 $i$ 的前进总量"，只讲前一半是不完整的证明。
3. nextval 只改常数因子，不改量级、也不改匹配结果，且丢掉了"最长相等前后缀"的语义——问语义必须回到 next。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）。整个「串」章的 408 真题全部落在这一篇上，而且三道题正好考了三件不同的事：

• 给失配位置，问下一轮的 $i$ 和 $j$（2015 年）。题面直接给出"第一次失配时 $i=j=5$"，问下次从哪儿开始比。做法固定两步：先算出失配位置的 next 值，再套"$i$ 不动、$j\leftarrow \text{next}[j]$"。四个选项就是把这两个动作各错一半——i=1,j=0 是 BF 的退法，i=5,j=0 是记住了 $i$ 不动却把 $j$ 归零，i=6,j=2 是 next 算对了但 $i$ 跟着 +1。
• 数从头到匹配成功的字符比较次数（2019 年）。列出上面那张逐步表，失配那一次要计入，$j$ 回退本身不计入。选项里差 1 的那个就是漏算了失配那次，差 2 的那个是把回退也算成了比较。
• 给"修正后的 next"，问模式串向右滑动的最长距离（2024 年）。滑动距离 $=j-\text{nextval}[j]$，对所有 $j$ 取最大值。这道题的干扰项正是"用原始 next 算"——两张表算出的最大滑动距离不一样，题面写了"修正后"就必须用 nextval。

还有一件事必须先做：认口径。 这三道真题两套编号都出现过——2015 与 2019 那两道在题干里约定的是"$next[j]$ = 最长真前缀=真后缀的长度"（0 起点），2024 那道约定的是"长度 + 1"（1 起点）。题干里那句约定不是废话，是这道题的计算前提，读题时先把它圈出来。

易错：失配时让 $i$ 也动了。 KMP 里只有匹配成功才让 $i$ 前进，失配时 $i$ 一步不退也一步不进。

易错：把 $j\leftarrow \text{next}[j]$ 记成 $j\leftarrow 0$ 或 $j\leftarrow 1$。 那等于丢掉已匹配的前缀信息，退化成 BF。

易错：数比较次数时漏掉失配的那一次，或把 $j$ 的回退也算成比较。 前者少算，后者多算。

易错：题面说"修正后的 next"却用原始 next 去算。 两张表的滑动距离不同，结果直接错。

易错：修正规则写成 $\text{next}[\text{next}[j]]$。 相等时应取 $\text{nextval}[\text{next}[j]]$，否则跳不到底。

易错：照搬记熟的那套口径去做题。 先读题干的约定，0 起点与 1 起点整体差 1。

教材出处

• 严蔚敏、李冬梅、吴伟民《数据结构（C 语言版）》（第 2 版），第 4 章 4.3.3 节，印刷第 93–94 页：KMP 算法的引入。指出"每当一趟匹配过程中出现字符比较不等时，不需回溯 $i$ 指针，而是利用已经得到的'部分匹配'的结果将模式向右'滑动'尽可能远的一段距离后，继续进行比较"，并给出式 (4-1)～(4-3) 的推导，即本篇式 (1)(2) 的来源。
• 同书印刷第 95 页：next 函数的定义式 (4-4)（三行分段：$j=1$ 取 0、取满足前后缀相等条件的最大 $k$、其他取 1），以及 KMP 匹配过程的文字描述与算法 4.2 Index_KMP。
• 同书印刷第 97 页：算法 4.3「计算 next 函数值」get_next，并给出 $T=\text{"abaabcac"}$ 的 next 值 $01122312$（图 4.8）；同页指出算法 4.3 的时间复杂度为 $O(m)$。
• 同书印刷第 97 页：next 函数的缺陷说明，以模式 "aaaab" 与主串 "aaabaaaab" 为例，指出 $i=4$、$j=4$ 失配后按 next 还要进行 $j=3,2,1$ 三次多余比较；由此给出算法 4.4「计算 next 函数修正值」get_nextval（印刷第 97–98 页），以及 "aaaab" 的 next $01234$ 与 nextval $00004$（图 4.9）。
• 同书印刷第 97 页：「虽然 BF 算法的时间复杂度是 $O(n\times m)$，但在一般情况下，其实际的执行时间近似于 $O(n+m)$……KMP 算法仅当模式与主串之间存在许多'部分匹配'的情况下，才显得比 BF 算法快得多。但是 KMP 算法的最大特点是指示主串的指针不需回溯，整个匹配过程中，对主串仅需从头至尾扫描一遍。」

相关知识

BF 算法（对照组与动机来源）｜ 串的基本概念（下标从 1 的约定，是 +1 与哨兵 0 的前提）｜ 从 KMP 到工业级全文搜索（超纲延伸）｜ 查找的基本概念、查找算法的分析及应用

相关文章

• 串的基本概念
• 朴素模式匹配（BF 算法）
• 拓展：从 KMP 到工业级全文搜索

交互体验

前往完整可视化页面 →

真题练习

相关真题（3题）

2024Q62分2019Q92分2015Q82分