KMP与BF模式匹配算法

115 阅读 0 评论 76 点赞

我是靠谱客的博主重要小海豚，最近开发中收集的这篇文章主要介绍KMP与BF模式匹配算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

看书看到了模式匹配算法，然后网上查了好多资料，好像明白了一点点。当然关于这方面博主July的博客说的特别详细，特别好，我看了很有收获，而我写这个只是为了加深自己的理解而已。若有不当，敬请斧正！下面是July大神的链接：

http://blog.csdn.net/v_JULY_v/

字符串匹配方法很多，经典的有BF和KMP算法。下面S表示目标串，T表示模式串。

BF算法：

又称蛮力匹配算法。顾名思义就是一个一个的匹配。拿T的第一个和S的第一个进行匹配，相等的话就用T的下一个与S的下一个进行比较。不同的话就拿T的第一个和S的下一个进行比较。这样一直循环直到匹配完全。

其算法思想很简单，但其算法时间复杂度较高，在最坏情况为O（tlen * slen）。究其原因，因为在T与S某一个字符匹配不上的话，S就要回去，这样有回溯，重复操作。为了减少回溯，这时就产生了KMP算法。

KMP算法：

KMP算法每当T与S匹配时出现字符比较不等，这时S不需要回溯，而是利用已经得到的“部分匹配”结果将T向右滑动一段距离，然后继续进行比较，这样就降低了时间复杂度。利用KMP算法的时间复杂度是O（tlen+slen）。

效果如下：

a b a b d f c S a b a b d f c S

a b d f T 当进行第一次匹配时： a b d f T 红的代表字符不等的

这个时候如果是BF，就会有回溯即：

BF： a b a b d f c S

a b d f T

而我们希望的是这样滑动即KMP：

KMP： a b a b d f c S

a b d f T

所以为了运用KMP算法，则就要有个数组来保存滑动距离，即next ，还有个在next基础上得到的nextval，两个虽然不同，但是表示的意思和作用是一样的，接下来我主要分析nextval 。

在讲这个之前需要先了解一些概念，就是串的前缀和后缀。如abcd的前缀有三个，分别为abc、ab、a，其后缀也有三个bcd、cd、d。

然后对一个T串移动一位，如下：

a b d f

a b d f 从红字中得到的是T的前缀和后缀。这样的往下推的话当再移动一位的时候得到的仍是T的前缀和后缀，即 a b 和d f。由此得到，滑动的距离nextval[i]其实就是T[0`j-1]中前缀与后缀相等的数目。

而KMP的实质就是针对待匹配的模式串的特点，判断它是否有重复的字符，从而找到它的前缀与后缀，进而求出相应的nextval数组，最终根据nextval数组而进行KMP匹配。

则程序如下：

#include "iostream"
using namespace std;
int GetNextVal(int* nextval ,char* T , int len)
{
int i = 0;
int j = -1;
nextval[i] = -1;
while(i < len - 1){
if(j == -1 || T[i] == T[j]){
++ i; ++ j;
if(T[i] != T[j]) nextval[i] = j;
else nextval[i] = nextval[j];
}else j = nextval[j];
}
return 0;
}
int KMPSearch(char* S ,const int slen ,char* T ,const int tlen , int* nextval)
{
int i = 0, j = 0;
while(i <= slen - 1 && j <= tlen - 1){
if(nextval[j] == -1 || S[i] == T[j]){
++ i; ++ j;
}else j = nextval[j];
}
if(j > tlen - 1) return i - tlen;
else return 0;
}
int main()
{
char* S = "asdasdassdgdfgkjdflkjldkflgndlkgkdkjfhjksdhkshkdjfshgkjdhfkgjhdkfjhgdfg";
char* T = "jdflkjl";
int* nextval = (int* )malloc(sizeof(int) * strlen(T));
GetNextVal(nextval ,T , strlen(T));
int pos = KMPSearch(S ,strlen(S) ,T ,strlen(T) , nextval);
printf("%d " , pos);
return 0;
}

结果如下：