4. KMP 算法的实现

2027 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

## 4. KMP 算法的实现

通过上述分析，可写出求解 next 数组的程序如下：

void get_next(SString T, int next[]){
int i = 1, j = 0;
next[1] = 0;
while (i < T.length) {
if (j == 0 || T.ch[i] == T.ch[j]) {
++i; ++j;
next[i] = j;
}
// 若 $p_i = p_j$，则 next[j+1] = next[j] + 1
}
else
j = next[j];
// 否则令 j = next[j]，循环继续
}
}


计算机上执行的效率很高，但手工计算时，仍需采用前文介绍的直观方法。

与 next 数组的求解相比，KMP 算法的匹配过程相对简洁，其结构与简单模式匹配极为相似。关键区别在于：当发生失配时，主串指针 $i$ 保持不变，仅将模式串指针 $j$ 回退至 next[j] 所指示的位置，并继续比较；特别地，当 $j = 0$ 时，将 $i$ 和 $j$ 同时加 1。也就是说，若模式串首字符失配，则将模式串向右滑动一位，下一轮匹配从主串第 $i+1$ 个位置开始。具体实现如下：

<!-- page: 129 -->

第4章 串
117

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


尽管简单模式匹配的最坏时间复杂度为 $O(mn)$，而KMP算法可达到 $O(m + n)$，但在一般情况下，简单模式匹配的平均执行时间往往接近 $O(m + n)$，因此至今仍被采用。KMP算法仅在主串与模式串存在大量“部分匹配”时才显著优于暴力匹配，其核心优点在于主串指针不回溯。

## 4.2.3 KMP算法的进一步优化

**参阅图5** &gt; nextval 数组的计算（2024）

前面定义的 next 数组在某些情况下仍存在缺陷，还可进一步优化。图 4.5 展示了一个典型示例：模式串 'aaaab' 与主串 'aaabaaaab' 进行匹配。

|  主串 | a | a | a | b | a | a | a | a | b  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  模式串 | a | a | a | a | b |  |  |  |   |
|  j | 1 | 2 | 3 | 4 | 5 |  |  |  |   |
|  next[j] | 0 | 1 | 2 | 3 | 4 |  |  |  |   |
|  nextval[j] | 0 | 0 | 0 | 0 | 4 |  |  |  |   |

图 4.5 KMP 算法的进一步优化示例

当 $i = 4$、$j = 4$ 时，主串字符 $s_4$ 与模式串字符 $p_4$（$b \neq a$）失配。若使用之前的 next 数组，则还需依次进行 $s_4$ 与 $p_3$、$s_4$ 与 $p_2$、$s_4$ 与 $p_1$ 的三次比较。然而，由于 next[4] = 3 且 $p_3 = p_4 = a$，同理 next[3] = 2 且 $p_2 = p_3 = a$，next[2] = 1 且 $p_1 = p_2 = a$，由于这些回退位置上的字符均与 $p_4$ 相同，继续比较只会重复同样的失配过程，造成不必要的开销。

问题根源在于：不应出现 $p_3 = p_{\text{next}[j]}$。理由是：当 $p_3 \neq s_i$ 时，下一轮将用 $p_{\text{next}[j]}$ 与 $s_i$ 比较；若 $p_{\text{next}[j]} = p_3$，则相当于用与 $p_3$ 相同的字符去匹配已知不等的 $s_i$，结果必定仍是失配。

那么，若出现 $p_3 = p_{\text{next}[j]}$，应如何处理？

此时应不断将 next[j] 替换为 next[next[j]]，直到找到某个位置 k，使得 $p_3 \neq p_k$ 或 $k = 0$ 为止，修正后的新数组称为 nextval 数组。计算 nextval 数组的算法如下（匹配算法不变）。

void get_nextval(SString T, int nextval[]) {
int i = 1, j = 0;
nextval[1] = 0;
while (i &amp;lt; T.length) {
if (j == 0 || T.ch[i] == T.ch[j]) {
++i; ++j;
if (T.ch[i] != T.ch[j]) nextval[i] = j;
else nextval[i] = nextval[j];
}
else
j = nextval[j];
}
}

&lt;!-- page: 130 --&gt;

2027年数据结构考研复习指导

KMP算法对于初学者来说可能不太容易掌握，强烈建议读者结合配套课程学习。

## 4.2.4 本节试题精选

### 一、单项选择题

01. 设有两个串 $S_1$ 和 $S_2$，求 $S_2$ 在 $S_1$ 中首次出现的位置的运算称为（）。

A. 求子串

B. 判断是否相等

C. 模式匹配

D. 连接

02. KMP算法的特点是在模式匹配时，指示主串的指针（）。

A. 不会变大

B. 不会变小

C. 都有可能

D. 无法判断

03. 设主串的长度为 $n$，子串的长度为 $m$，则简单的模式匹配算法的时间复杂度为（），KMP算法的时间复杂度为（）。

A. $O(m)$

B. $O(n)$

C. $O(mn)$

D. $O(m + n)$

04. 在KMP算法中，用next数组存放模式串的部分匹配信息，当模式串位 $j$ 与主串位 $i$ 比较时，两个字符不相等，则 $j$ 的位移方式是（）。

A. $j = 0$

B. $j = j + 1$

C. $j$ 不变

D. $j = \text{next}[j]$

05. 在KMP算法中，用next数组存放模式串的部分匹配信息，当模式串位 $j$ 与主串位 $i$ 比较时，两个字符不相等，则 $i$ 的位移方式是（）。

A. $i = \text{next}[i]$

B. $i$ 不变

C. $i = 0$

D. $i = i + 1$

06. 串&#x27;ababaaababaa&#x27;的next数组为（）。

A. $0,1,2,3,4,5,6,7,8,9,9$

B. $0,1,2,1,2,1,1,1,1,2,1,2$

C. $0, 1, 1, 2, 3, 4, 2, 2, 3, 4, 5, 6$

D. $0, 1, 2, 3, 0, 1, 2, 3, 2, 2, 3, 4, 5$

07. 设主串 $S = &#x27;aabaaaba&#x27;$，模式串 $T = &#x27;aaab&#x27;$，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（）。

A. 10

B. 9

C. 8

D. 7

08. 设主串 $S = &#x27;aabaaaba&#x27;$，模式串 $T = &#x27;aaab&#x27;$，采用改进后的KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（）。

A. 9

B. 8

C. 7

D. 6

09. KMP算法使用 nextval 数组进行模式匹配，模式串为 $S = &#x27;ababaaa&#x27;$，当主串中的某个字符与 $S$ 中的第6个字符失配时，$S$ 向右滑动的距离是（）。

A. 1

B. 2

C. 3

D. 4

10.【2015统考真题】已知字符串s为&#x27;abaabaabacacaabaabcc&#x27;，模式串t为&#x27;abaabc&#x27;。采用KMP算法进行匹配，第一次出现“失配”（s[i]≠t[j]）时，$i = j = 5$，则下次开始匹配时，$i$ 和 $j$ 的值分别是（）。

A. $i = 1, j = 0$

B. $i = 5, j = 0$

C. $i = 5, j = 2$

D. $i = 6, j = 2$

11. 【2019统考真题】设主串 $T = &#x27;abaabaabcabaabc&#x27;$，模式串 $S = &#x27;abaabc&#x27;$，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（）。

A. 9

B. 10

C. 12

D. 15

12. 【2024统考真题】KMP算法使用修正后的next数组进行模式匹配，模式串为 $S = &#x27;aabaab&#x27;$，当主串的某个字符与 $S$ 的某个字符失配时，$S$ 向右滑动的最长距离是（）。

A. 5

B. 4

C. 3

D. 2

### 二、综合应用题

01. 在字符串模式匹配的KMP算法中，求模式的next数组值的定义如下：

&lt;!-- page: 131 --&gt;

第4章 串
119

$$
\text{next}[j] = \begin{cases}
0, &amp;amp; j = 1 \\
\max\{k\}1 &amp;lt; k &amp;lt; j &amp;amp; \text{且 } p_1 \cdots p_{k-1} = p_{j-k+1} \cdots p_{j-1} \end{cases}, \\
1, &amp;amp; \text{其他情况}
$$

1）当 $j = 1$ 时，为什么要取 $\text{next}[1] = 0$？
2）为什么要取 $\max\{k\}$，$k$ 最大是多少？
3）其他情况是什么情况，为什么取 $\text{next}[j] = 1$？

02. 设有字符串 $S = \text{&#x27;aabaabaabaac&#x27;}$，$P = \text{&#x27;aabaac&#x27;}$。

1）求出 $P$ 的 next 数组。
2）若 $S$ 作为主串，$P$ 作为模式串，试给出 KMP 算法的匹配过程。

## 4.2.5 答案与解析

### 一、单项选择题

01. C

求子串操作是从串 S 中截取第 $i$ 个字符起长度为 1 的子串，选项 A 错误。选项 B、D 明显错误。

02. B

在 KMP 算法的比较过程中，主串不会回溯，所以主串的指针不会变小。

03. C、D

尽管实际应用中，一般情况下简单的模式匹配算法的时间复杂度近似为 $O(m + n)$，但它的理论时间复杂度还是 $O(mn)$。KMP 算法的时间复杂度为 $O(m + n)$。

04. D

在 KMP 算法中，当主串的第 $i$ 个字符和模式串的第 $j$ 个字符不匹配时，主串的位指针 $i$ 不变，将主串的第 $i$ 个字符与模式串的第 $\text{next}[j]$ 个字符比较，即 $j = \text{next}[j]$。

05. B

在 KMP 算法中，当主串的第 $i$ 个字符和模式串的第 $j$ 个字符失配时，主串指针 $i$ 不回溯。

06. C

本题采用先求串 $S = \text{&#x27;ababaaababaa&#x27;}$ 的部分匹配值，再求 next 数组的方法。

- &#x27;a&#x27; 的前后缀都为空，最长相等前后缀长度为 0。
- &#x27;ab&#x27; 的前缀 $\{a\} \cap$ 后缀 $\{b\} = \emptyset$，最长相等前后缀长度为 0。
- &#x27;aba&#x27; 的前缀 $\{a, ab\} \cap$ 后缀 $\{a, ba\} = \{a\}$，最长相等前后缀长度为 1。
- &#x27;abab&#x27; 的前缀 $\{a, ab, aba\} \cap$ 后缀 $\{b, ab, bab\} = \{ab\}$，最长相等前后缀长度为 2。

依次求出的部分匹配值见下表第 3 行，将其整体右移一位，低位用 -1 填充，见下表第 4 行。

|  编号 | 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  |
|  PM | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 | 6  |
|  next | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5  |

选项中 $\text{next}[1]$ 等于 0，所以将 next 数组整体加 1。

07. B

假设位序从 1 开始，手工计算出 T 的 next 数组如下。

|  编号 | 1 | 2 | 3 | 4  |
| --- | --- | --- | --- | --- |
|  S | a | a | a | b  |
|  next | 0 | 1 | 2 | 3  |

&lt;!-- page: 132 --&gt;

2027年数据结构考研复习指导

采用 KMP 算法时：第一趟，经过 3 次比较后，发现 S[3]≠T[3]；第二趟，用 S[3] 和 T[2]（next[3]=2）比较，不相等；第三趟，用 S[3] 和 T[1]（next[2]=1）比较，不相等；第四趟，next[1]=0，因此开始用 S[4] 和 T[1] 比较，经过 4 次比较后，匹配成功。整个匹配过程如下。

|   | a | a | b | a | a | a | b | a  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  第一趟 | a | a | a | b |  |  |  |   |
|  第二趟 |  | a | a | a | b |  |  |   |
|  第三趟 |  |  | a | a | a | b |  |   |
|  第四趟 |  |  |  | a | a | a | b |   |

总比较次数为 $3 + 1 + 1 + 4 = 9$。

## 08. C

假设位序从 1 开始，计算出 T 的 nextval 数组如下。

|  编号 | 1 | 2 | 3 | 4  |
| --- | --- | --- | --- | --- |
|  S | a | a | a | b  |
|  nextval | 0 | 0 | 0 | 3  |

采用改进的 KMP 算法时：第一趟，经过 3 次比较后，发现 S[3]≠T[3]；第二趟，nextval[3]=0，因此开始用 S[4] 和 T[1] 比较，经过 4 次比较后，匹配成功。整个匹配过程如下。

|   | a | a | b | a | a | a | b | a  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  第一趟 | a | a | a | b |  |  |  |   |
|  第二趟 |  |  |  | a | a | a | b |   |

总比较次数为 $3 + 4 = 7$。

## 09. B

假设位序从 0 开始，计算出 nextval 数组。当比较到 S[j] 失配时，模式串向右滑动的距离为 j- nextval[j]（$0 \leqslant j \leqslant 6$），由下图可知，当 j=5 时向右滑动的距离为 $5 - 3 = 2$。

|  编号 j | 0 | 1 | 2 | 3 | 4 | 5 | 6  |
| --- | --- | --- | --- | --- | --- | --- | --- |
|  S[j] | a | b | a | b | a | a | a  |
|  next[j] | -1 | 0 | 0 | 1 | 2 | 3 | 1  |
|  nextval[j] | -1 | 0 | -1 | 0 | -1 | 3 | 1  |
|  j-nextval[j] | 1 | 1 | 3 | 3 | 5 | 2 | 5  |

此外，若对 KMP 算法很熟悉，则此类题也可直接动手模拟，而不需要求 nextval 数组，与第 6 个字符匹配失败，说明前面的 ababa 匹配成功，S 可向右滑动 2 位继续尝试匹配。

匹配失败，说明此元素不是 a

主串：a b a b a  ①  ②  ③  ④

第一趟匹配 模式串：a b a b a a a

此元素继续与元素 b 比较

主串：a b a b a  ①  ②  ③  ④

第二趟匹配 模式串：a b a b a a a

## 10. C

由题中“失配 s[i]≠t[j] 时，i=j=5”，可知题中的主串和模式串的位序都是从 0 开始的（要注意灵活应变）。按照 next 数组生成算法，对于 t 有

|  编号 | 0 | 1 | 2 | 3 | 4 | 5  |
| --- | --- | --- | --- | --- | --- | --- |
|  t | a | b | a | a | b | c  |
|  next | -1 | 0 | 0 | 1 | 1 | 2  |

&lt;!-- page: 133 --&gt;

第4章 串
121

发生失配时，主串指针 i 不变，子串指针 j 回退到 next[j] 位置重新比较，当 s[i] ≠ t[j] 时，i = j = 5，由 next 表得知 next[j] = next[5] = 2（位序从 0 开始）。因此，i = 5，j = 2。

## 11. B

假设位序从 0 开始，按照 next 数组生成算法，对于 S 有

|  编号 | 0 | 1 | 2 | 3 | 4 | 5  |
| --- | --- | --- | --- | --- | --- | --- |
|  S | a | b | a | a | b | c  |
|  next | -1 | 0 | 0 | 1 | 1 | 2  |

第一趟连续比较 6 次，在模式串的 5 号位和主串的 5 号位匹配失败，模式串的下一个比较位置为 next[5]，即下一次比较从模式串的 2 号位和主串的 5 号位开始，然后直到模式串的 5 号位和主串的 8 号位匹配，第二趟比较 4 次，匹配成功。单个字符的比较次数为 10 次。

## 12. A

假设位序从 0 开始，计算出 nextval 数组。当比较到 S[j] 失配时，模式串向右滑动的距离为 j- nextval[j]（0 ≤ j ≤ 5），由下图可知，当 j = 4 时向右滑动的距离最长，此时距离为 5。

|  编号 j | 0 | 1 | 2 | 3 | 4 | 5  |
| --- | --- | --- | --- | --- | --- | --- |
|  S[j] | a | a | b | a | a | b  |
|  next[j] | -1 | 0 | 1 | 0 | 1 | 2  |
|  nextval[j] | -1 | -1 | 1 | -1 | -1 | 1  |
|  j-nextval[j] | 1 | 2 | 1 | 4 | 5 | 4  |

## 二、综合应用题

### 01. 【解答】

1）当模式串的第 1 个字符与主串的当前字符比较不相等时，next[1] = 0，表示模式串应右滑一位，主串当前指针后移一位，再和模式串的第 1 个字符进行比较。

2）当主串的第 i 个字符与模式串的第 j 个字符失配时，主串 i 不回溯，则假定模式串的第 k 个字符与主串的第 i 个字符比较，k 值应满足条件 1 &amp;lt; k &amp;lt; j 且 &#x27;p_i ··· p_{k-1}&#x27; = &#x27;p_{j-k+1} ··· p_{j-1}&#x27;&#x27;，即 k 为模式串的下次比较位置。k 值可能有多个，为了不使向右滑动丢失可能的匹配，右滑距离应该取最小，因为 j-k 表示右滑的距离，所以取 max{k}。k 的最大值为 j-1。

3）除上面两种情况外，发生失配时，主串指针 i 不回溯，在最坏情况下，模式串从第 1 个字符开始与主串的第 i 个字符比较。

### 02. 【解答】

1）P=&#x27;aabaac&#x27;，按照 next 数组生成算法，对于 P 有：

① 设 next[1] = 0，next[2] = 1。

|  编号 | 1 | 2 | 3 | 4 | 5 | 6  |
| --- | --- | --- | --- | --- | --- | --- |
|  S | a | a | b | a | a | c  |
|  next | 0 | 1 |  |  |  |   |

② j = 3 时 k = next[j-1] = next[2] = 1，观察 S[j-1]（S[2]）与 S[k]（S[1]）是否相等，S[2] = a，S[1] = a，S[2] = S[1]，所以 next[j] = k + 1 = 2。

j-1=2
a a b a a c
a a b a a c
↑k=1

<!-- page: 134 -->

2027年数据结构考研复习指导

③ $j = 4$ 时 $k = \text{next}[j-1] = \text{next}[3] = 2$，观察 $\text{S}[j-1]$（$\text{S}[3]$）与 $\text{S[k]}(\text{S}[2])$ 是否相等，$\text{S}[3] = \text{b}$，$\text{S}[2] = \text{a}$，$\text{S}[3] != \text{S}[2]$。

\begin{array}{rl}
&amp;amp; \downarrow j - 1 = 3 \\
\text{a a b a a c} \\
&amp;amp; \text{↑k=2}
\end{array}


此时 $k = \text{next}[k] = 1$，观察 S[3] 与 S[k] (S[1]) 是否相等，S[3] = b，S[1] = a，S[3] != S[1]。 $k = \text{next}[k] = 0$，因为 $k = 0$，所以 $\text{next}[j] = 1$。

\begin{array}{rl}
&amp;amp; \downarrow j - 1 = 3 \\
\text{a a b a a c} \\
&amp;amp; \text{↑k=0}
\end{array}


④ $j = 5$ 时 $k = \text{next}[j-1] = \text{next}[4] = 1$，观察 $\text{S}[j-1]$（$\text{S}[4]$）与 $\text{S[k]}(\text{S}[1])$ 是否相等，$\text{S}[4] = \text{a}$，$\text{S}[1] = \text{a}$，$\text{S}[4] = \text{S}[1]$，所以 $\text{next}[j] = k + 1 = 2$。

\begin{array}{rl}
&amp;amp; \downarrow j - 1 = 4 \\
\text{a a b a a c} \\
&amp;amp; \text{↑k=1}
\end{array}


⑤ $j = 6$ 时 $k = \text{next}[j-1] = \text{next}[5] = 2$，观察 $\text{S}[j-1]$（$\text{S}[5]$）与 $\text{S[k]}(\text{S}[2])$ 是否相等，$\text{S}[5] = \text{a}$，$\text{S}[2] = \text{a}$，$\text{S}[5] = \text{S}[2]$，所以 $\text{next}[j] = k + 1 = 3$。

\begin{array}{rl}
&amp;amp; \downarrow j - 1 = 5 \\
\text{a a b a a c} \\
&amp;amp; \text{↑k=2}
\end{array}


最后的结果为

|  编号 | 1 | 2 | 3 | 4 | 5 | 6  |
| --- | --- | --- | --- | --- | --- | --- |
|  S | a | a | b | a | a | c  |
|  next | 0 | 1 | 2 | 1 | 2 | 3  |

也可以通过求部分匹配值表的方法来求 next 数组。

2）利用KMP算法的匹配过程如下。

第一趟：从主串和模式串的第1个字符开始比较，失配时 $i = 6$，$j = 6$。

|  主串 | a | a | b | a | a | b | a | a | b | a | a | c  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | a | a | b | a | a | c |  |  |  |  |  |   |

第二趟：next[6] = 3，主串当前位置和模式串的第3个字符继续比较，失配时 $i = 9$，$j = 6$。

|  主串 | a | a | b | a | a | b | a | a | b | a | a | c  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   |  |  |  | a | a | b | a | a | c |  |  |   |

第三趟：next[6] = 3，主串当前位置和模式串的第3个字符继续比较，匹配成功。

|  主串 | a | a | b | a | a | b | a | a | b | a | a | c  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   |  |  |  |  |  |  | a | a | b | a | a | c  |

<!-- page: 135 -->

第4章 串
123