KMP算法（深入理解）

KMP算法的主要核心是next数组的获取，要想深刻的理解KMP算法需要一个沉淀的过程。对于研究过KMP算法的小伙伴来说，应该知道，next数组是用于匹配串当前位置的定位，一切的一切都是为了避免像暴力算法那样不停的回溯。先贴出代码，后面再详细说。

[注]：下面代码的kmp是从0号位置开始匹配的，不同于天勤数据结构树上是从1开始的。

#include<stdio.h>
#include<stdlib.h>

typedef struct{
    char *ch;
    int length;
}Str;

int strassign(Str& str,char *ch);
int strlength(Str str);
int strcompare(Str str1,Str str2);
int concat(Str& str,Str str1,Str str2);
int subString(Str& subStr,Str str,int pos,int len);
int cleardtring(Str& str);
int simpleIndex(Str str,Str subStr);
void getNext(Str subStr,int *next);
void getBetterNext(Str subStr,int *next);
int KMPIndex(Str str,Str subStr,int *next);

int main(){

    Str str1,str2;
    char s1[]="qwertyuiopasdfghjklzxcvbnm";
    char s2[]="ghjkl";
    strassign(str1,s1);
    strassign(str2,s2);

    //暴力匹配
    /** **/
    int pos1=simpleIndex(str1,str2);
    printf("查询得到的位置%d\n",pos1);


    //KMP匹配
    /****/
    int next[5];
    getNext(str2,next);
    int pos2=KMPIndex(str1,str2,next);
    printf("KMP查询得到的位置%d\n",pos2);


    return 0;
}
/**类的初始化**/

int strassign(Str& str,char *ch){
    char *c=ch;
    int len=0;
    if(str.ch){
        free(str.ch);
    }
    while(*c){
        ++len;
        ++c;
    }
    if(len==0){
        str.ch=NULL;
        str.length=0;
        return 1;
    }else{
        str.ch=(char*)malloc(sizeof(char)*(1+len));
        if(str.ch==NULL){
            return 0;
        }else{
            c=ch;
            for(int i=0;i<=len; ++i,++c){
                str.ch[i]=*c;
            }
            str.length=len;
            return 1;
        }
    }

}

/**简单暴力字符串匹配**/
int simpleIndex(Str str,Str subStr){
    int i=0,j=0,k=i;
    while(i<str.length&&j<subStr.length){
        if(str.ch[i]==subStr.ch[j]){
            ++i;
            ++j;
        }else{
            j=0;//字串指针归于1号位置;
            i=++k;//主串跳向下一轮匹配
        }
    }
    if(j>=subStr.length){
        return k;
    }else return -1;//表示匹配失败;
}
/**获取next数组**/
void getNext(Str subStr,int *next){
    int i=0,j=-1;
    /**第一个位置作为特殊标记位置，当跳回到此位置时候
    主串位置需要移动，而匹配串不需要加一
    正常情况下两者都要加一
    所以为了代码的统一编写把初始的next[0]减置为-1
    在if里面加一个条件即可实现“j不变，i加1”
    如果第一个正常设置为0，那么在while循环里面就要写成


> if(j!=0&&subStr.ch[i]==subStr.ch[j]){
>             ++i;
>             ++j;
>             next[i]=j;
>         }else if(j==0&&subStr.ch[i]==subStr.ch[j]){
>           ++i;
>         }else{……}

    **/
    next[0]=-1;
    while(i<subStr.length-1){
        /**
        注意此处，这个循环的意义在于用next[i]的值求取next[i+1]的值
        所以是先执行++i，然后再对next进行赋值
        并且循环是到length-2位置的
        **/
        if(j==-1||subStr.ch[i]==subStr.ch[j]){
            ++i;
            ++j;
            next[i]=j;
        }else{
            /**如果当前i、j对应的字符不相等则next[i+1]不能加一
            j=next[next[j]],在循环中直到满足当前字符相等
            next[i]=++j便可以执行
            **/
            j=next[j];
        }

    }
}
void getBetterNext(Str subStr,int *next){
    int i=0,j=-1;
    next[0]=-1;
    while(i<subStr.length-1){

        if(j==-1||subStr.ch[i]==subStr.ch[j]){
            ++i;
            ++j;
            /**
            改进next数字组,比如出现如……UIGKAAAAAAABBC……情况时，
            当匹配到C时不匹配跳到了最后一个A，依然不匹配，
            没改进的next只会回跳一个，
            改进后的直接跳到第一个A的前面，即K。
            改进的地方，在于当t回跳后要让比较的字符不等于原来失配字符，这样下一回才有可能匹配成功。
            **/
            if(subStr.ch[i]!=subStr.ch[j]){
                next[i]=j;
            }
        }else{
            j=next[j];
        }

    }
}
/**KMP字符串匹配**/
int KMPIndex(Str str,Str subStr,int *next){
    int i=0,j=0;
    while(i<str.length&&j<subStr.length){
        if(j==-1||str.ch[i]==subStr.ch[j]){
            ++i;
            ++j;
        }else{
            j=next[j];
        }
    }
    if(j>=subStr.length){
        return i-subStr.length;
    }else return -1;
}

为什么主串可以不回溯呢？
因为使用字串匹配到当前位置依旧没有得到结果，那么当前位置之前的子主串是一定不能得出结果的，最多最多我们可以使用与当前字符相邻的并于模式串已经部分匹配的部分（即回溯一小部分，进一步我们可以将主串的小跨度回溯转化为模式串匹配指针的移动从而实现主串指针的完全不回溯），于是只需计算next数组，“它代替了回溯”。

时间复杂度
计算next数组为O(m),主串遍历为O(n),即其时间复杂度为O(m+n)。

计算next公式
(1)如果当前字符Pj与Pt相同，则next[j+1]=next[j]+1
(next[j]的值是t，即next[j]=t+1)。
(2)否则t=next[t]，继续判断当前字符是否满足（1），直到满足为止否则一直循环。
如下图·，解释一波：

再结合上面代码及其注释，应该容易看懂。