字符串模式匹配————BF、KMP算法基础详解

时间:2023-01-13 06:13:01

模式匹配:

假设有两个字符串string(s代替)和pattern(p代替),其中pattern是要在string中查找的模式。即确定pattern是否在string中并返回其坐标数值。这一过程就称模式匹配。

c语言中最基本的就是..strstr函数,但是其效率不高,自己定义的算法完全可以做得更好。

介绍KMP算法之前,先介绍一下最简单的暴力枚举的算法(KMP是在这个算法的基础上改进而来的)

1.BF_Match(BF:brute froce,暴力枚举)

  

 举例说明:

S: ababcababa

P: ababa

BF算法匹配的步骤如下

字符串模式匹配————BF、KMP算法基础详解

(补充一下,当i回溯的时候,即“失配”(s[i] != p[j])时)  以上过程图摘自:http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html

下面给出实现代码:

<span style="font-family:Microsoft YaHei;font-size:14px;">/*——————暴力匹配——————
注意const的用法,去掉之后编译会出现waring,看看
*/
#include <stdio.h>
#include <string.h>
int BFmatch(const char *s, const char *t)
{
int i = 0;
while(i < strlen(s))
{
int j = 0;
while(s[i] == t[j] && j < strlen(t))
{
i++;
j++;
}
if(j == strlen(t))
return i - strlen(t);
i = i - j + 1;//为什么是i - j + 1画一下图就明白了..
}
return 0;
}
int main()
{
const char * s = "ababcababa";
const char * t = "ababa";

int pos = BFmatch(s,t);
printf("The position is : %d\n",pos);
return 0;
} </span>
算法分析:

我们可以看出,i并不是线性的推进(经常回溯...)所以这个肯定效率不高,当p不是s的模式匹配的话,时间复杂度是O(m * n) m是s长度,n是p的长度。

理想的时间复杂度是O(strlen(string) + strlen(pattern)),于是三个大牛就想出来了一个算法。

2.KMP算法

D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)

下面是KMP算法的流程,非常重要!!

假定:

pattren = “a b c a b c a c a b"

字符串s:

s = s[0]s[1]s[2].........s[m-1]

假设要判断是否存在从s[i]开始的匹配。

1.如果s[i] != a(p[0]),那么显然下次从s[i+1]与a比较。

2.如果s[i] = a 但是 s[i+1] != b(p[1]),那么显然进行s[i+1]与a的比较。

3.如果s[i]s[i+1] = "ab",但是s[i+2] != c,即下述情况。

(以上的分析作为基础,需要好好理解一下,不成问题)

s = ".....a b ? ? ? ? ......"

其中s的第一个?代表 s[i+2] != c,因此,搜索的下一步应该是对s[i+2]和a(p[0])比较!

(这是显而易见的,BF做法的话i就要回溯到i+1了,但其实没有必要回溯,因为s[i]s[i+1] = "ab"是既定事实,即s[i+1]是b(p[1])了,绝对不可能是a了)————这句话是KMP的一个重点。

依次类推,当出现下述情况时:

 s = "....a b c a? ? . . . ?"

  p = " ab c a b c a c a b"

假定出现了pattern前四个字母的匹配,然后失配,即s[i+4] != b 

通过观察可以得出,匹配搜索可以继续把s[i+4]与p的第二个字符b(红色标记)进行比较。而不必进在s中对i进行回溯,这就是我们想要的线性算法。

(以上的分析是线性算法的由来,理解KMP算法的第一步)

如果上述的文字搞得大家云里雾里,不妨看下面这张图:

字符串模式匹配————BF、KMP算法基础详解

在阐述了原理之后,我们剩下一个最主要的问题:

出现失配的情况下,应当将p字符串向右滑动多少?

实现这个过程,就是KMP算法的核心。

为了解决这个问题,引入了一个函数————模式失配函数。(引自《数据结构》(c语言版))

(PS:如果不明白这个函数的意义,请看此链接:http://www.java3z.com/cwbwebhome/article/article19/re022.html?id=3731

*模式失配函数:

定义模式失配函数为:next[]。

如果说next[j] = k,表明如果s[i] != p[j]的时候,j应该回溯到的pattern字符串的位置!                          

举例说明:

   j   0  1  2  3   4   5  6   7  8  9  10

p[j] A  B  R  A  C  A  D  A  B  R  A

      next[j]  -1  0  0   0   1  0   1  0   1  2  3 

默认情况下next[0] = -1,这是一个标示符,因为如果说next[j] = -1 即说明pattern的第一个字符就失配了,此时j不需要回溯,单纯的设置为-1

根据失配函数的定义,得到如下模式匹配规则

1.如果出现了形如s[i-j]s[i-j+1]...s[i-1] = p[0]p[1]....p[j-1]且s[i] != p[j]的部分匹配,那么,若j != -1 则下一次模式匹配时,比较失配字符s[i]和p[next[j]]

2.若j = -1 ,则继续比较s[i+1]和p[0],代码如下:

/*-----------------------------------算法4.6/4.7------------------------
-------------------------------------KMP-------------------------------
-----------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#define maxn 10005
int next[maxn];
int KMP(char *s,char *p,int start_pos)
{
int i = start_pos,j = 0;

while(i < strlen(s)){
if(s[i] == p[j] || j == -1){
++i;
++j;
}
else
j = next[j];
if(j == strlen(p))
return start_pos + (i - j);
}
return -1;
}
void GetNext(char *s)
{
int j = 0, k = -1;

next[0] = -1;
while(s[j] != '\0'){
if(s[j] == s[k] || k == -1){
j++;
k++;
next[j] = k;
}
else
k = next[k];
}
}
int main()
{
char s[maxn] = {0};
char p[maxn] = {0};

scanf("%s",s);
scanf("%s",p);
int start_pos = 0;
GetNext(p);
int ans = KMP(s,p,start_pos);
printf("%d\n",ans);
return 0;
}

__________________________________________________________________________________________________________________________________________________________

会发现,next和KMP的写法很相近。

其实next就是把pat自己和自己进行模式匹配。

具体的证明————严蔚敏老师的《数据结构》有讲,而且很详细。