数据结构严薇敏——KMP算法之next数组优化代码实现

￡神魔★判官ぃ 2022-05-18 06:14 189阅读 0赞

**前面实现的next数组依然还有缺陷，当模式串中失配元素很多相同的前缀，有一部分的比较是不需要的。**

**例如下面这种情况可以明显看出：**

![70][]

**因为模式串中第1、2、3个字符和第4个字符都相等，因此不需要要再和第四个字符比较，而可以直接进行i = 5, j = 1时的字符比较，这里就是需要优化的部分。 **

### **实现代码：** ###

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXSIZE 255
    
    typedef unsigned char SString[MAXSIZE + 1];   //0号用来存放串的长度
    
    void Get_Nextval(SString T,int *nextval)
    {
        int i = 1;    //初始化i表示后缀
        int j = 0;    //初始化j表示前缀
        nextval[1] = 0;
        while( i < T[0] )
        {
            if( j == 0 || T[i] == T[j])
            {
                ++i;
                ++j;
                if(T[i] != T[j])
                    nextval[i] = j;
                else
                    nextval[i] = nextval[j];
            }
            else
                j = nextval[j];
        }
    }
    int Index_KMP(SString S,SString T,int pos)
    {
        int i = pos;
        int j = 1;
        int nextval[5];
        Get_Nextval(T,nextval);
        while(i <= S[0] && j <= T[0])
        {
            if(j == 0 || S[i] == T[j])
            {
                i++;
                j++;
            }
            else
                j = nextval[j];
        }
        if(j > T[0])
            return i - T[0];
        else
            return 0;
    }
    int main()
    {
    
        SString T = " aaaab";             //模式串
        T[0] = 5;                   //存放串长
        SString S = " abbaaaaba";
        S[0] = 9;
        printf("模式串：%s\n主串为：%s\n",T,S);
        printf("位置为：%d\n",Index_KMP(S,T,2));
        printf("\n");
        return 0;
    }

严薇敏

[70]: /images/20220518/4576ad9f609e4e4fa6b66ddbfa7e42bd.png