字符串匹配:KMP算法的实现以及理解

时间:2023-01-07 00:03:22

这篇是 算法 类别中的第一篇,大二学的数据结构,平时写项目也几乎没有用过,很多常见算法的实现都不能记清了。

以后每天复习点,然后写写对复习到的数据结构和算法的理解。


我们先来看一种简单的好理解的字符串匹配算法,这里我用c语言实现这个算法

#include<stdio.h>
#include<Windows.h>
using namespace std;
int Index(char *, char *);
int getStrLength(char *);

int main(){
int res = Index("acabaabaabcacaabc", "abaabcac");
printf("position = %d\n", res);
system("pause");
return 0;
}
/*
*字符串匹配函数
*S为主串 该例子中为 cabcabb
*T为模式串 该例子中为 abb
*/
int Index(char *S, char *T){
//i,j 分别为要匹配的S,T字符的位置
int i = 0;
int j = 0;
//sLength,tLength 分别为S,T的长度
int sLength = getStrLength(S);
int tLength = getStrLength(T);
/*
*如果主串匹配到尽头 i >= sLength 这种情况就是主串匹配完了,假设这时候j < tLength 说明未匹配上
*或者模式串匹配到尽头 j >= tLength 这种情况就是模式串匹配完毕,即匹配上
*/
while (i < sLength && j < tLength){
//如果当前对应字符匹配,就继续进行下一个字符的比较
if (S[i] == T[j]){
i++;
j++;
}
//否则,即是不对应,这时候主串的i就要退到开始匹配的位置的下一位
//j要退到0位,模式串每次都要从头匹配 !!!(这就是KMP和普通算法的区别)!!!
else{
i = i - j + 1;
j = 0;
}
}
//如果循环结束后 j >= tLength,实际上只可能等于,就说明匹配上了,当前i位置减去T的长度就是匹配上的第一个字符的位置
if (j >= tLength)
return i - tLength;
//否则就返回 -1 标识没有匹配上
else
return -1;
}

//自实现一个函数返回传入字符串的长度
int getStrLength(char *S){
int count = 0;
while (*S != '\0'){
S ++;
count ++;
}
return count;
}


这是很简单思路的字符串匹配,从主串第0位开始匹配,如果模式串匹配完了,就成功,否则就从头和主串下一位开始匹配

算法的最坏情况复杂度为O(n*m)     n,m为两个串的长度

中间打!!!的部分已经提到了普通匹配算法的劣势,我们举例说明一下

上述算法我们传入的

主串为 acabaabaabcacaabc 模式串为 abaabcac

下面我们用S,T来表示主串和模式串

假设匹配到下面的这个位置(上下对应,S[7]和T[5]比较 *记住我们是从0开始的*)

第n次匹配

S      acabaabaabcacaabc

T          abaabc 

这时候没有匹配上,如果按上述算法我们就要从S[3]开始和T[0]比较

S      acabaabaabcacaabc

T            a

这样的话,只要没有匹配上,之前匹配的操作都等于白执行了

而且,在很长的文本匹配中,可能主串中多次出现和模式串部分匹配的字段

有没有办法利用上之前的匹配操作呢?


KMP算法就是基于这个思想,利用上“部分匹配”的记过将模式串尽可能的向右“滑动够远的距离

例,第n次匹配后就可以这样

S      acabaabaabcacaabc

T                aba

直接由S[7]和T[2]比较

为什么可以这样呢?

我们观察模式串  发现模式串中有重复的字段(单个重复字符其实也可以利用上的,这里我们拿好理解的来)

abaabcac

我们从第n次匹配就可以知道 abaab这部分是匹配上的,呢么主串中就含有这部分字符串

直接由S[7]和T[2]比较

为什么可以这样呢?

我们由第n次匹配可以知道 abaab这部分是匹配上的,呢么主串中就含有这部分字符串

呢只要我们对模式串自身进行分析,分析出来模式串自身对于自身的匹配情况

那样,出现这种部分匹配的情况时候,我们的 主串S 的 i 就不用回退

只要求得模式串T从哪个位置开始匹配就可以了


int Index_KMP(char *S, char *T){
int i = 0;
int j = 0;
int sLength = getStrLength(S);
int tLength = getStrLength(T);

int *next = get_next(T);

while (i < sLength && j < tLength)
{
if (j == 0 || S[i] == T[j]){
i ++;
j ++;
}
else{
j = next[j];//和之前的Index函数对比,这个地方我们并没有回退i,只是通过一个next数组,得出T[j]从哪里开始
}
}

if (j >= tLength)
return i - tLength;
else
return -1;
}

下面就是KMP算法的重点,求出next[]数组


int* get_next(char *T){
//i标识T当前字符的位置
int i = 0;
//j标识前一个字符的next[i]
int j = -1;
int tLength = getStrLength(T);
//动态数组,长度为T的长度
int *next = (int*)malloc(sizeof(int) * tLength);
//我们设模式串第一个字符的next[] = -1
//因为当模式串第一个字符就和主串不匹配时候,必然是直接去匹配主串下一个字符
next[0] = -1;
while (i < tLength){
/*
* j == -1的时候,说明模式串第一个字符就匹配不上主串,这时候就应该和主串下一个字符匹配,所以i++; *
* 而且next[1]也肯定是0,就是说当模式串第二个字符匹配失败时候,我们肯定是直接从模式串第一位重新匹配的
* 这里我们把next[0] = -1的优势在于建立了一种统一。具体下面阐述
*/
if (j == -1 || T[i] == T[j]){
i ++;
j ++;
next[i] = j;
}
/*
*这里我们为什么让j等于next[j]呢?请大家思考一下,下面我会有解释
*/
else{
j = next[j];
}
}
return next;
}


这里我建立一个对应的表

i             0 1 2 3 4 5 6 7

模式       a b a a b c a c

next[i]   -1 0 0 1 1 2 0 1

我们根据这个表来逐步分析一下这个算法

这个算法就是根据当前字符是否和自身匹配来得出来下一个字符的next[]

首先next[0] = -1 ,next[1] = 0 

当i = 1时候 ,T[1] != T[0]    (T[0]中的0来自于next[1] 后面都是如此)

如果和第0个都不匹配的话,就没办法向后滑动,所以next[2] = 0 只能老老实实从第一个开始匹配

当i = 2时候,T[2] == T[0],说明这个字符和第一个字符相等

那样的话,T[3]匹配出现错误时候,因为T[3]前一个字符和第一个字符相等了,那么这部分就不用比对了,直接比对T[1]和主串当前字符就可以了

当i = 3时候  T[3] != T[1]    *这里我们要详尽说明一下为什么 else 时  j = next[j]*

i = 3时候可以用下图表示

                                             0 1 2 3 4 5 6 7

模式串自身作为主串 T             a b a a b c a c

模式串和自身进行匹配 T1   a b

这时候为什么要 j = next[j]呢?

因为 T[3]T1[next[3]]不匹配,我们就这时候把T1当成一个模式串,T当成一个主串

T1[1]不匹配了,这时候就应该让 T1[next[1]] 和主串进行比对

这里就充分体现了自身和自身比对去找出规律

这时候T[3] == T1[0]  这种情况就和i = 2时候一样了

之后的分析,大家可以自己进行一下,前面三个分析就已经包含所有情况了。


虽然KMP算法最坏情况也是 O[n*m]  但是但实际的字符串匹配中,部分匹配的情况很多,而且我们主串根本不用回退,所以它的执行效率还是不错的


第一次去分析算法,才发现自己当初学的时候,对算法的理解并不透彻,很难去阐述出来为什么要这么做,

这也体现了,看懂和能自己写,自己写和给别人讲明白,真的是不同的境界

自己足足斟酌了几个小时,才写下来自己的分析,而且我仍然觉得自己讲的有点不明白

这也坚定了我要对自己以前掌握的算法都一一分析的决心