408数据结构——串的模式匹配：朴素模式匹配算法（暴力匹配）+KMP算法

￡神魔★判官ぃ 2022-10-09 00:33 227阅读 0赞

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