数据结构总目录
KMP
- KMP字符串匹配算法
-
- 1. 简单模式匹配算法的正向匹配
-
- 1.1 图文解析
- 1.2 源代码
- 1.3 测试结果
- 2. 简单模式匹配算法的反向匹配
-
- 2.1 图文解析
- 2.2 源代码
- 2.3 测试结果
- 3. KMP字符串匹配算法
-
- 3.1 图文解析
- 3.2 源代码
- 3.3 测试结果
KMP字符串匹配算法
KMP算法是一种对简单模式匹配算法进行改进的字符串匹配算法
由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。
KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
1. 简单模式匹配算法的正向匹配
1.1 图文解析
存在主字符串 mainStr 和需要匹配的子串 subStr若发生匹配失败,主串指针回退到起点的下一个位置,子串指针则从头开始![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法 ![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法
1.2 源代码
#include <stdio.h>
int MatchSearch(char *mainStr, char *subStr, int len1, int len2)
{
int i = 0, j = 0;
while (i < len1 && j < len2)
{
if (mainStr[i] == subStr[j])
{
// 向后匹配
++i;
++j;
}
else
{
// 主串指针回退到起点的下一个位置
i = i - j + 1;
// 子串指针从头开始
j = 0;
}
}
return j >= len2 ? i - len2 : -1;
}
int main()
{
char mainStr[10] = "ababaababc";
char subStr[5] = "ababc";
int pos = MatchSearch(mainStr, subStr, 10, 5);
if (pos > -1)
{
printf("匹配成功: %d\n", pos);
}
else
{
printf("匹配失败!\n");
}
return 0;
}
1.3 测试结果
2. 简单模式匹配算法的反向匹配
2.1 图文解析
观察下图的简单匹配过程,我们可以发现
其实在a和c发生不匹配时,就可以判断出主串中[0,4](ababa)与子串(abaac)不匹配了
![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法 于是我们可以直接从子串结尾处开始进行判断
若发生不匹配,则回退到结尾处的下一个位置
![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法 若匹配成功,则可以反向进行匹配![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法 ![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法
2.2 源代码
#include <stdio.h>
int MatchSearch(char *mainStr, char *subStr, int len1, int len2)
{
int i = len2 - 1, j = len2 - 1;
// 从子串的最后一个位置开始查询
while (i < len1 && j >= 0)
{
// 向前匹配
if (mainStr[i] == subStr[j])
{
--i;
--j;
}
else
{
// 主串指针回退到开始位置的下一个位置
i = i + (len2 - 1 - j) + 1;
// 子串指针结尾开始
j = len2 - 1;
flag = i - len2 + 1;
}
}
return j < 0 ? i + 1 : -1;
}
int main()
{
char mainStr[10] = "ababaababc";
char subStr[5] = "ababc";
int pos = MatchSearch(mainStr, subStr, 10, 5);
if (pos > -1)
{
printf("匹配成功: %d\n", pos);
}
else
{
printf("匹配失败!\n");
}
return 0;
}
2.3 测试结果
3. KMP字符串匹配算法
3.1 图文解析
一、观察如下图,我们发现在发生在不匹配位置之前的字符串【abab】是相同的,且存在最大相同前后缀序列【ab】那么我们便可以根据最大相同前缀序列进行快速移动子串,如下图:![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法 ![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法 ![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法
二、于是我们可以根据最大相同前后缀序列,将下次快速移动的位置存储在一个辅助数组中next【】中代表当subStr[i]与主串发生不匹配时,可以根据next[i]快速定位下次匹配的位置为j![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法 可以理解为简单模式匹配算法的反向匹配过程中,进行反向搜索的快速定位![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法 ![]()
数据结构_KMP字符串匹配算法(C语言)数据结构总目录KMP字符串匹配算法
3.2 源代码
#include <stdio.h>
void InitNext(int *next, char *subStr, int len)
{
next[0] = -1;
// (后缀结束下标 i) 和 (前缀结束下标 j)
int i = 0, j = -1;
while (i < len)
{
if (j == -1 || subStr[i] == subStr[j])
{
i++;
j++;
next[i] = j;
}
else
{
// 重新定位相同前缀、后缀的位置
j = next[j];
}
}
}
int KMPSearch(char *mainStr, char *subStr, int len1, int len2)
{
int next[len2];
int i = 0, j = 0;
// 初始化next数组
InitNext(next, subStr, len2);
// 根据next数组进行快速定位查找
while (i < len1 && j < len2)
{
if (j == -1 || mainStr[i] == subStr[j])
{
i++;
j++;
}
else
{
// 根据next数组快速定位下一个匹配的子串位置
j = next[j];
}
}
return j >= len2 ? i - len2 : -1;
}
int main()
{
char mainStr[10] = "ababaababc";
char subStr[5] = "ababc";
int pos = KMPSearch(mainStr, subStr, 10, 5);
if (pos > -1)
{
printf("匹配成功: %d\n", pos);
}
else
{
printf("匹配失败!\n");
}
return 0;
}