欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}