求NEXT数组和KMP匹配的两种写法

注释掉的是我不喜欢的写法。

//计算串str的next数组
void getnext(char *str){
    int len=strlen(str);
    int j=0,k=-1;
    next[0]=-1;
    while(j<len){
        if(k==-1||str[j]==str[k]) next[++j]=++k;
        else k=next[k];
    }
}

/*
void getnext(char *str){
    int len=strlen(str);
    next[0]=next[1]=0;
    for(int i=1;i<len;i++){
        int j=next[i];
        while(j&&str[i]!=str[j]) j=next[j];//一直回溯j直到str[i]==str[j]或j减小到0
        next[i+1]=str[i]==str[j]?j+1:0;//更新next[i+1]
    }
}
*/

//返回串S中第一次出现串T的开始位置
int KMP(char *S,char *T){
    int l1=strlen(S), l2=strlen(T);
    int i=0,j=0;
    while(i<l1){
        if(j==-1||S[i]==T[j])
            i++, j++;
        else j=next[j];
        if(j==l2) return i-l2+1;
    }
    return -1;
}

/*
int KMP(char *S,char *T){
    int l1=strlen(S),l2=strlen(T);
    int i=0,j=0;
    for(int i=0;i<l1;i++){
        while(j&&S[i]!=T[j]) j=next[j];
        if(S[i]==T[j]) j++;
        if(j==l2) return i-l2+1;
    }
    return -1;//若一直匹配不成功则返回-1
}
*/