前言
本文内容源于对《数据结构（C语言版）》（第2版）、王道讲解学习所得心得、笔记整理和总结，以便复习。
可搭配以下链接一起学习：
【考研】《数据结构》知识点总结.pdf_考研数据结构知识点总结-其它文档类资源-CSDN文库
【2023考研】数据结构常考应用典型例题（含真题）_住在阳光的心里的博客-CSDN博客
目录
前言
一、基本概念
二、KMP算法
三、KMP算法的进一步优化
四、习题
一、基本概念
1、串的模式匹配：子串（即模式串）的定位操作，即求子串在主串中的位置。
例1：设有两个串S1 和串S2 ，求 S2 在 S1 中首次出现的位置的运算称为模式匹配。
2、字符串的前缀、后缀和部分匹配值
（1）前缀：除最后一个字符以外，字符串的所有头部子串。
（2）后缀：除第一个字符以外，字符串的所有尾部子串。
（3）部分匹配值：字符串的前缀和后缀的最长相等前后缀长度。
例2：以 ‘ ababa ’ 为例：
| 串 | 前缀 | 后缀 | 前后缀交集 | 最长相等前后缀长度 |
| ‘ a ’ | 空集 | 空集 | 空集 | 0 |
| ‘ ab ’ | { a } | { b } | 空集 | 0 |
| ‘ aba ’ | { a, ab } | { a, ba } | { a } | 1 |
| ‘ abab ’ | { a, ab, aba } | { b, ab, bab } | { ab } | 2 |
| ‘ ababa ’ | { a, ab, aba, abab } | { a, ba, aba, baba } | { aba } | 3 |
所以，串 S 的 ‘ ababa ’ 的部分匹配值为 00123，部分匹配值（Partial Match，PM）的表如下：
| 编号 | 1 | 2 | 3 | 4 | 5 |
| S | a | b | a | b | a |
| PM | 0 | 0 | 1 | 2 | 3 |
二、KMP算法
已知：右移位数 = 已匹配的字符数 – 对应的部分匹配值
写成：Move = (j – 1) – PM[j – 1]
针对例 2 ，PM 表右移一位，得到 next 数组：
| 编号 | 1 | 2 | 3 | 4 | 5 |
| S | a | b | a | b | a |
| next | -1 | 0 | 0 | 1 | 2 |
改写成：Move = (j – 1) – next[j]
相当于将子串的比较指针回退到 j = j – Move = next[j] + 1，
为了使公式更简洁，将 next 数组整体加1：
| 编号 | 1 | 2 | 3 | 4 | 5 |
| S | a | b | a | b | a |
| next | 0 | 1 | 1 | 2 | 3 |
即子串指针变化公式为 j = next[j]。
在实际匹配过程中，子串在内存里是不会移动的，而是指针在变化。
next[j] 的含义：在子串的第 j 个字符与主串发生失配时，则跳到子串的 next[j] 位置重新与主串当前位置进行比较。
当模式串第一个字符 (j =1) 与主串第 i 个字符发生失配时，规定 next[1] = 0。将模式串右移一位，从主串的下一个位置 (i + 1) 和模式串的第一个字符继续比较。
例3：求模式串的 next 值：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 模式 | a | b | a | a | b | c | a | b | a |
| next[j] | 0 | 1 | 1 | 2 | 2 | 3 | ? | ? | ? |
上表中，已求得6个字符的 next 值，现求 next[7]。
解法一：（选择题中常用方法）
‘a’，最长相等前后缀长度为 0
’ab’，最长相等前后缀长度为 0
‘aba’，最长相等前后缀长度为 1
‘abaa’，最长相等前后缀长度为 1
‘abaab’，最长相等前后缀长度为 2
‘abaabc’，最长相等前后缀长度为 0
‘abaabca’，最长相等前后缀长度为 1
‘abaabcab’，最长相等前后缀长度为 2
‘abaabcaba’，最长相等前后缀长度为 3
串 S 的 ‘abaabcaca’ 的部分匹配值为 0 0 1 1 2 0 1 2 3
PM 表右移一位，得到 next 数组：-1 0 0 1 1 2 0 1 2
next 数组整体加1：0 1 1 2 2 3 1 2 3
由此可知，next[7] = 1; next[8] = 2; next[9] = 3;
解法二：
关键点：若
，则需比较 (因 next[3] = 1)，
由于，则 next[8] = next[7] + 1 = 2;
求 next[9]，因
从 j = 2 开始，依次判断 ？
不相等：nextval[j] = next[j]
相等：将 next[j] 修正为 next[next[j]]，直至两者不相等为止。
步骤1：令 nextval[1] = next[1] = 0
步骤2：j = 2, next[j] = next[2] = 1, 则 p2 = b ≠ p1 = a，nextval[2] = next[2] = 1
步骤3：j = 3, next[j] = next[3] = 1, 则 p3 = p1 = a，则 nextval[3] = nextval[next[3]] = nextval[1] = 0
步骤4：j = 4, next[j] = next[4] = 2, 则 p4 = p2 = b，则 nextval[4] = nextval[next[4]] = nextval[2] = 1
步骤5：j = 5, next[j] = next[5] = 3, 则 p5 = p3 = a，则 nextval[5] = nextval[next[5]] = nextval[3] = 0
步骤6：j = 6, next[j] = next[6] = 4, 则 p6 = a ≠ p4 = b，则 nextval[6] = next[6] = 4
步骤7：j = 7, next[j] = next[7] = 2, 则 p7 = a ≠ p2= b，则 nextval[6] = next[7] = 2
步骤8：j = 8, next[j] = next8] = 2, 则 p8 = p2= b，则 nextval[8] = nextval[next[8]] = nextval[2] = 1
步骤9：j = 9, next[j] = next[9] = 3, 则 p9 = p3= a，则 nextval[9] = nextval[next[9]] = nextval[3] = 0
步骤10：j=10, next[10] = 4, 则 p10 = p4= b,则 nextval[10] = nextval[next[10]] = nextval[4] = 1
步骤11：j=11, next[11] = 5, 则 p11 = p5= a,则 nextval[11] = nextval[next[11]] = nextval[5] = 0
步骤12：j=12, next[12] = 6, 则 p12 = p6= a,则 nextval[12] = nextval[next[12]] = nextval[6] = 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 |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
| nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 | 1 | 0 | 4 |
串 ‘ababaaababaa’ 的 nextval 数组为 0 1 0 1 0 4 2 1 0 1 0 4
由上述推理可知，答案选C。
【注意】
在步骤 5 的推理中， 和 )，注意到此时 nextval[3] 的值已存在，故直接将 nextval[5]赋值为 nextval[3]。
对于一般情况，nextval 数组是从前往后逐步求解的，
发生
由上表知 next[5] = 2，即 j = 2。
4、【2019统考真题】设主串T = ‘ abaabaabcabaabc ‘, 模式串 s = ‘abaabc’, 采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是( B )。
A. 9 B. 10 C.12 D. 15
解：模式串 s = ‘abaabc’，最长相等前后缀长度有：
‘a’，最长相等前后缀长度为 0
‘ab’，最长相等前后缀长度为 0
‘aba’，最长相等前后缀长度为 1
‘abaa’，最长相等前后缀长度为 1
‘abaab’，最长相等前后缀长度为 2
‘abaabc’，最长相等前后缀长度为 0
所以，模式串 s = ‘abaabc’ 的部分匹配值 PM 为 001120
将 PM 右移一位，得 next 数组为 -1 0 0 1 1 2，即如下表：
| 编号 | 0 | 1 | 2 | 3 | 4 | 5 |
| s | a | b | a | a | b | c |
| next | -1 | 0 | 0 | 1 | 1 | 2 |
【注意】如果串的位序是从 1 开始的，则 next 数组需要整体加1，若串的位序从 0 开始，则 next 数组不需要整体加 1。
| 编号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 主串 | a | b | a | a | b | a | a | b | c | a | b | a | a | b | c |
| 第一趟 | a | b | a | a | b | c | |||||||||
| 失败， 比较了6次 | |||||||||||||||
| 第二趟 | a | b | a | a | b | c | |||||||||
| 开始比较 | 成功， 比较了4次 |
第一趟连续比较 6 次，在模式串的 5 号位和主串的 5 号位匹配失败，模式串的下一个比较位置为 next[5] = 2，即下一次比较从模式串的 2 号位和主串的 5 号位开始，然后直到模式串 5 号位和主串8 号位匹配，第二趟比较 4 次，模式串匹配成功。
单个字符的比较次数为10次，因此选B。