串的模式匹配算法KMP

简单匹配模式算法

对一个串中某子串的定位操作称为串的模式匹配,其中待定位的子串称为模式串。
·算法的基本思想为:从主串的第一个位置起和模式串的第一个字符开始比较,如果相等,则继续逐一比较后续字符;否则从主串的第二个字符开始,再重新用上一步的方法与模式串中的字符作比较,以此类推,直到比较完模式传中的所有字符。若匹配成功,则返回模式串在主串中的位置;若匹配不成功,则返回一个可区别于主串所有位置的标记,如”0”.
算法实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Str{
char *ch;
int length;
};
//字符串储存在1-length的位置上
int index(Str str,Str substr){
int i=1,j=1,k=i;
while(i<=str.length &&j<=substr.length){
if(str.ch[i]==substr.ch[j]){
++i;
++j;
}
else{
j=1;
i=++k; //匹配失败,从主串的下一位置开始
}
}
if(j>substr.length) return k; //匹配成功
else return 0;
}

较好情况下此算法的时间复杂度为O(n+m),n和m分别为主串和模式的长度。然而,在有些情况下,该算法的效率却很低。如当模式串为’00000001’,而主串为’00000000000000000000000000000000000000000000000000001’时,由于模式中前7个字符均为”0”,又主串前52个字符均为”0”,每趟比较都在模式的最后一个字符出现不等,此时需将指针i回溯到i-6的位置上,并从模式的第一个字符开始重新比较,整个匹配过程中指针i需回溯45次,算法在这种最坏情况下的时间复杂度为O(n×m),所以可作如下改进。

KMP算法

该算法的改进在于:每一趟匹配过程中出现字符比较不等时,不需回溯i指针,而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较。
· 令next[j]=k,即表明当模式中第j个字符与主串中相应字符“失配”时,在模式中需重新和主串中该字符进行比较的字符的位置为k。
模式串next函数的定义:

例如模式串abaabcac的next[j]依次为01122312
若在匹配过程中S[i]=P[j],则i和j分别增1,否则j再退到下一个next值得位置,依次类推,直到下列两种可能:
· 一种是j退到某个next值时字符比较相等,则指针各自增1,继续进行匹配;
· 另一种是j退到值为0(即模式的第一个字符“失配”),则此时需将模式继续向右滑动一个位置,即从主串的下一个字符S[i+1]起和模式重新开始匹配。

1
2
3
4
5
6
7
8
9
10
11
12
//由模式直接求得next数组
void getnext(Str substr,int next[]){
int i=1,j=0;
next[1]=0;
while(i<substr.length){
if(j==0||substr.ch[i]==substr.ch[j]){
++i;
++j;
next[i]=j;
}else j=next[j];
}
}

得到next数组后,将简单模式匹配算法稍作修改就可由状态S[k]直接跳到S[k+1]的改进算法

1
2
3
4
5
6
7
8
9
10
11
12
13
//KMP算法
void KMP(Str str,Str substr,int next[]){
int i=1,j=1;
while(i<=str.length && j<=substr.length){
if(j==0||str.ch[i]==substr.ch[j]){
++i;
++j;
}else j=next[j];
}
if(j>substr.length)
return i-substr.length;
else return 0;
}

KMP算法的改进

(待)