KMP算法

目录

1.由来

 1.1暴力匹配算法

1.2KMP 

2.术语

3.核心思想

4.算法主体

5.NEXT[ ]的构建 

NEXT[]数组的构建步骤

1. 初始化NEXT[]数组

2. 构建NEXT[]数组的循环过程

3. 逐步填充NEXT[]数组

第一步：计算 NEXT[1]

第二步：计算 NEXT[2]

第三步：计算 NEXT[3]

第四步：计算 NEXT[4]

4.最终NEXT[]数组

构建NEXT[]数组的过程总结

代码演示： 

 6.代码实现

7.考研408真题 

2015年

2019年 

---

1.由来

 1.1暴力匹配算法

（又称朴素字符串匹配算法）是最基础的字符串匹配方法。它的核心思想是逐一比较主串中的字符和子串中的字符，直到找到匹配或者遍历完成。
我们来举一个例子：
主串："ababcabcacbab" 子串："abcac"
暴力匹配过程：
从主串的第一个字符开始，逐字符比较：
主串第1到第5个字符是 "ababc"，与子串 "abcac" 比较：第1个字符 'a' 匹配 'a'
第2个字符 'b' 匹配 'b'
第3个字符 'a' 不匹配 'c'
发生不匹配，移动主串的起始位置，继续比较。
从主串的第二个字符开始，比较：
主串第2到第6个字符是 "babca"，与子串 "abcac" 比较：第1个字符 'b' 不匹配 'a'
发生不匹配，继续向后移动。
从主串的第三个字符开始，比较：
主串第3到第7个字符是 "abcab"，与子串 "abcac" 比较：第1个字符 'a' 匹配 'a'
第2个字符 'b' 匹配 'b'
第3个字符 'c' 匹配 'c'
第4个字符 'a' 匹配 'a'
第5个字符 'b' 不匹配 'c'
发生不匹配，继续向后移动。
从主串的第四个字符开始，比较：
主串第4到第8个字符是 "bcabc"，与子串 "abcac" 比较：第1个字符 'b' 不匹配 'a'
发生不匹配，继续向后移动。
从主串的第五个字符开始，比较：
主串第5到第9个字符是 "cabca"，与子串 "abcac" 比较：第1个字符 'c' 不匹配 'a'
发生不匹配，继续向后移动。
从主串的第六个字符开始，比较：
主串第6到第10个字符是 "abcac"，与子串 "abcac" 完全匹配！
此时找到匹配位置，暴力匹配算法在主串的第6个字符处找到了子串 "abcac"。整个过程就是依次比较每个字符，当不匹配时就从下一个字符开始重新比较。

像上述的暴力匹配的时间复杂度就是O(n*m)，为了将时间复杂度降为线性的，KMP算法应运而生。 

1.2KMP 

KMP算法之所以被称为“KMP算法”，是源自其三位发明者的姓氏首字母缩写：

• Knuth（唐纳德·克努斯）
• Morris（詹姆斯·H·莫里斯）
• Pratt（沃恩·普拉特）

这三位计算机科学家在1977年共同发表了这项算法，用于高效地在文本中查找子字符串。KMP算法通过预处理模式串，构建部分匹配表（也称为“失配表”），从而在搜索过程中避免了不必要的重复比较，大大提高了匹配的效率。

总结来说，KMP算法的名称直接来源于其创始人的姓氏首字母，体现了他们对这一经典字符串匹配算法的贡献。

2.术语

在KMP算法中，有几个重要的术语，理解这些术语有助于更好地掌握算法的工作原理：

1. 主串（Text）：要在其中查找子串的字符串，通常用“T”表示。

2. 子串（Pattern）：要查找的目标字符串，通常用“P”表示。

3. 部分匹配表（Partial Match Table）或失配表（Failure Function）：一个数组，存储了子串的每个前缀的最长相等前后缀的长度。这个表用于在匹配失败时，决定子串在主串中应该向右移动多少位。

4. 前缀（Prefix）：字符串的开头部分。例如，对于字符串“abc”，其前缀包括“a”、“ab”和“abc”。

5. 后缀（Suffix）：字符串的结尾部分。例如，对于字符串“abc”，其后缀包括“c”、“bc”和“abc”。

6. 最长相等前后缀（Longest Prefix Suffix, LPS）：在部分匹配表中，某个位置的值表示该位置的前缀和后缀中最长的相等部分的长度。例如，对于子串“abab”，最长相等前后缀是“ab”，其长度为2。

7. 匹配过程：KMP算法通过使用部分匹配表来优化字符比较。当发生不匹配时，算法不会回溯主串，而是根据部分匹配表的值，调整子串的位置，继续进行比较。

8. 时间复杂度：KMP算法的时间复杂度是O(n + m)，其中n是主串的长度，m是子串的长度。这是因为部分匹配表的构建和匹配过程都只需线性扫描。

了解这些术语有助于深入理解KMP算法的原理和实现过程。

3.核心思想

KMP算法由算法主体加上NEXT[]数组的构建组成。 

核心思想是：用已经掌握的信息来规避重复的运算；

主串指针永远不回溯；

匹配失败时，将模式串的前缀直接移动到后缀处，也即根据NEXT[ ]数组中的值决定向前跳过可以跳过的字符数量；

NEXT[ ]数组中的值代表字符串匹配失败时可以向前跳过的字符数量。

建立NEXT[ ]数组也就是寻找模式串中相同前后缀的长度。 

 

 

4.算法主体

int kmp_search(char *string, char *pattern) {int n = strlen(string);int m = strlen(pattern);int next[m];build_next(pattern, next);int i = 0, j = 0;while (i < n) {if (string[i] == pattern[j]) {i++;j++;}if (j == m) {return i - j;  // 返回匹配的位置} else if (i < n && string[i] != pattern[j]) {if (j != 0) {j = next[j - 1];} else {i++;}}}return -1;  // 未找到匹配
}

5.NEXT[ ]的构建 

在KMP算法中，NEXT[]数组（也叫部分匹配表或失配函数）用于存储每个位置之前的最长相等前缀和后缀的长度。它帮助KMP算法在发生不匹配时，决定子串应该跳过的字符数量，以避免重复比较，从而提高匹配效率。

NEXT[]数组的构建步骤

我们以子串 P = "abcab" 为例，演示如何构建 NEXT[] 数组。对于子串的每个位置 i，NEXT[i] 表示该位置之前的子串中最长的相等前后缀的长度。

1. 初始化NEXT[]数组

首先，NEXT[0] = -1，因为对于第一个字符没有前缀和后缀。

NEXT[] = [-1, 0, 0, 0, 0]

2. 构建NEXT[]数组的循环过程

构建过程中，我们维护两个指针 i 和 j：

• i：表示当前正在计算 NEXT[i] 的位置。
• j：表示当前最长相等前后缀的长度（也是 P[0] 到 P[j-1] 与 P[i-j] 到 P[i-1] 的匹配情况）。

算法步骤如下：

1. 初始条件：i = 1，j = 0。
2. 比较 P[i] 和 P[j]：
   • 如果相等，则 NEXT[i] = j + 1，然后同时增加 i 和 j。
   • 如果不相等且 j > 0，则设置 j = NEXT[j-1]，继续比较。
   • 如果 j = 0，直接设置 NEXT[i] = 0，然后 i++。

3. 逐步填充NEXT[]数组

第一步：计算 NEXT[1]

• i = 1，j = 0，比较 P[1] = 'b' 和 P[0] = 'a'。
• 不匹配，且 j = 0，所以 NEXT[1] = 0，然后 i++。

NEXT[] = [-1, 0, 0, 0, 0]

第二步：计算 NEXT[2]

• i = 2，j = 0，比较 P[2] = 'c' 和 P[0] = 'a'。
• 不匹配，且 j = 0，所以 NEXT[2] = 0，然后 i++。

NEXT[] = [-1, 0, 0, 0, 0]

第三步：计算 NEXT[3]

• i = 3，j = 0，比较 P[3] = 'a' 和 P[0] = 'a'。
• 匹配，NEXT[3] = j + 1 = 1，然后 i++，j++。

NEXT[] = [-1, 0, 0, 1, 0]

第四步：计算 NEXT[4]

• i = 4，j = 1，比较 P[4] = 'b' 和 P[1] = 'b'。
• 匹配，NEXT[4] = j + 1 = 2，然后 i++，j++。

NEXT[] = [-1, 0, 0, 1, 2]

4.最终NEXT[]数组

最终构建出的 NEXT[] = [-1, 0, 0, 1, 2]，表示对于子串 "abcab"，每个位置的最长相等前后缀的长度。

构建NEXT[]数组的过程总结

• NEXT[0] 通常初始化为 -1。
• 如果 P[i] == P[j]，则 NEXT[i] = j + 1，同时递增 i 和 j。
• 如果不匹配，且 j > 0，回退到 NEXT[j-1]，否则 NEXT[i] = 0。

NEXT数组的构建时间复杂度是 O(m)，其中 m 是子串的长度。

代码演示： 

void build_next(char *pattern, int *next) {int len = strlen(pattern);int i = 1, j = 0;  // 注意i从1开始，j从0开始next[0] = 0;  // next数组的第一个值为0while (i < len) {if (pattern[i] == pattern[j]) {j++;next[i] = j;i++;} else {if (j != 0) {j = next[j - 1];} else {next[i] = 0;i++;}}}
}

 6.代码实现

C语言完整实现： 

#include <stdio.h>
#include <string.h>void build_next(char *pattern, int *next) {int len = strlen(pattern);int i = 1, j = 0;  // 注意i从1开始，j从0开始next[0] = 0;  // next数组的第一个值为0while (i < len) {if (pattern[i] == pattern[j]) {j++;next[i] = j;i++;} else {if (j != 0) {j = next[j - 1];} else {next[i] = 0;i++;}}}
}int kmp_search(char *string, char *pattern) {int n = strlen(string);int m = strlen(pattern);int next[m];build_next(pattern, next);int i = 0, j = 0;while (i < n) {if (string[i] == pattern[j]) {i++;j++;}if (j == m) {return i - j;  // 返回匹配的位置} else if (i < n && string[i] != pattern[j]) {if (j != 0) {j = next[j - 1];} else {i++;}}}return -1;  // 未找到匹配
}int main() {char string[] = "abcabcabcabcd";char pattern[] = "abcabcd";int result = kmp_search(string, pattern);if (result != -1) {printf("Pattern found at index %d\n", result);} else {printf("Pattern not found\n");}return 0;
}

7.考研408真题 

2015年

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

 求得模式串的next[] = {0,0,1,1,2,0}

i不动（主串指针不回溯）

模式串指针跳到过j=2

故i=5,j=2。 

2019年 

【2019 统考真题】设主串 T='abaabaabcabaabc'，模式串S='abaabc'，采用 KMP算法进行模式匹配,到匹配成功时为止,在匹配过程中进行的单个字符间的比较次数是( )。 

求得模式串的next[] = {0,0,1,1,2,0}