408数据结构——串的模式匹配:朴素模式匹配算法(暴力匹配)+KMP算法
程序员文章站
2022-06-01 21:33:46
...
王道408数据结构第四章,串的模式匹配。
考试中不大可能考察KMP的算法代码,也不会考察KMP的优化,需要掌握手动求KMP的next数组,以及掌握朴素模式匹配算法及KMP算法的时间复杂度。
一、朴素模式匹配算法
最坏时间复杂度为O(mn),即每次都在最后一个字符时匹配失败。
最好时间复杂度为O(m),即一次就匹配成功,也有说法是O(1),因为一般模式串的长度都为常数级。
其中m表示模式串的长度,n表示主串的长度。
二、KMP匹配算法
优点是主串的指针i不需要回溯,模块向后滑动位数的计算仅与模式本身的结构有关,与主串无关。
最坏时间复杂度为O(m+n),其中计算next表需要O(m),进行匹配过程需要O(n)。
其中m表示模式串的长度,n表示主串的长度。
三、KMP手动计算next数组
KMP难点在于手动计算next数组。
next[j]的求法:
- next[1]:无脑写0
- next[2]:无脑写1
- 其他情况:在不匹配的位置前面,画一条分界线,模式串一步步往后(右)退,直到分界线之前的字符全部能对上,或模式串完全跨过分界线(即全部对不上),此时next数组值为j指向的值。
四、实现代码
#include <iostream>
#define MaxLen 255
using namespace std;
//定长顺序结构表示
typedef struct {
char ch[MaxLen+1]; //每个分量存储一个字符
int length; //串的实际长度
}SString;
//实现初始化一个串
void InitString( SString &S ) {
for( int i = 0; i <= MaxLen; i++ ) {
S.ch[i] = '\0'; //将串中每一个元素都初始化为'\0'
}
S.length = 0; //将串的长度初始化为0
}
//实现串的赋值操作
bool StrAssign(SString &T, char *chars ) {
char *c = chars;
int j;
for (j = 0; *c; j++, ++c)
;
if (j == 0 || j > MaxLen) //判断字符串的长度是否合法
return false;
else
{
T.length = j;
for (int i = 1; i <= T.length; i++)
{
T.ch[i] = chars[i - 1]; //将字符串赋给串
}
return true;
}
}
//朴素模式匹配算法,最坏时间复杂度为O(mn),最好时间复杂度为O(m)
//从主串S的第一个字符起,与模式T的第一个字符比较,若相等,则继续逐个比较后续字符;
//否则从主串的下一个字符起,重新和模式的字符比较
//以此类推,直至模式T的每个字符依此和主串S的一个连续的字符序列相等,则称匹配成功,函数值为与模式T中第一个字符相等的字符在主串S中的序号
//否则匹配不成功,函数值为0
int Index(SString S,SString T){
int i=1,j=1;
while(i<=S.length&&j<=T.length){
if (S.ch[i]==T.ch[j])
++i,++j; //首字符相等,继续比较后继字符
else{ //出现字符不相等,指针后退重新开始匹配
i=i-j+2; //i回到主串的下一个子串的第一个位置(i=i-j+1+1)
j=1; //j回到模式串的第一个位置
}
}
if (j>T.length)
return i-T.length; //匹配成功,返回序号
else
return 0; //匹配失败
}
//求next值
void get_next(SString T,int next[]){
int i=1,j=0;
next[1]=0;
while(i<T.length){
if (j==0||T.ch[i]==T.ch[j]){
++i;
++j;
next[i]=j; //若pi=pj,则next[j+1]=next[j]+1
}
else
j=next[j]; //否则令j=next[j],循环继续
}
}
//KMP,最坏时间复杂度为O(m+n),其中计算next表需要O(m),进行匹配过程需要O(n)
//相较于朴素模式匹配算法,主串的i指针不需要回溯,只需要修改模式串的j指针即可
int Index_KMP(SString S,SString T,int next[]){
int i=1,j=1;
while(i<=S.length&&j<=T.length){
if (j==0||S.ch[i]==T.ch[j]){
++i;
++j; //继续比较后继字符
}
else
j=next[j]; //模式串向右移动
}
if (j>T.length)
return i-T.length; //匹配成功
else
return 0;
}
int main() {
SString S,T;
InitString(S);
InitString(T);
StrAssign(S,"hello world!");
StrAssign(T,"world");
cout<<"朴素模式匹配算法:"<<Index(S,T)<<endl; //朴素模式匹配算法:7
int next[10000];
get_next(T,next);
cout<<"KMP匹配算法:"<<Index_KMP(S,T,next)<<endl; //KMP匹配算法:7
return 0;
}