目录
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算法中,有几个重要的术语,理解这些术语有助于更好地掌握算法的工作原理:
-
主串(Text):要在其中查找子串的字符串,通常用“T”表示。
-
子串(Pattern):要查找的目标字符串,通常用“P”表示。
-
部分匹配表(Partial Match Table)或失配表(Failure Function):一个数组,存储了子串的每个前缀的最长相等前后缀的长度。这个表用于在匹配失败时,决定子串在主串中应该向右移动多少位。
-
前缀(Prefix):字符串的开头部分。例如,对于字符串“abc”,其前缀包括“a”、“ab”和“abc”。
-
后缀(Suffix):字符串的结尾部分。例如,对于字符串“abc”,其后缀包括“c”、“bc”和“abc”。
-
最长相等前后缀(Longest Prefix Suffix, LPS):在部分匹配表中,某个位置的值表示该位置的前缀和后缀中最长的相等部分的长度。例如,对于子串“abab”,最长相等前后缀是“ab”,其长度为2。
-
匹配过程:KMP算法通过使用部分匹配表来优化字符比较。当发生不匹配时,算法不会回溯主串,而是根据部分匹配表的值,调整子串的位置,继续进行比较。
-
时间复杂度: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]
的匹配情况)。
算法步骤如下:
- 初始条件:
i = 1
,j = 0
。 - 比较
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}