[数据结构与算法]KMP算法（C语言）

#include<stdio.h>
int length(char *str){
    int i=0;
    while(str[i]!='\0'){
        i++;
    }
    return i;
}
void getNext(char *str,int next[]){
    int i=0,j=-1;
    next[0]=-1;
    while(i<length(str)-1){
        if(j==-1||str[i]==str[j]){
            next[++i]=++j;
        }else{
            j=next[j];
        }
    }
}
int KMP(char *txt,char *str){
    int next[length(str)];
    int i=0,j=0;
    getNext(str,next);
    while(i<length(txt)&&j<length(str)){
        if(j==-1||txt[i]==str[j]){
            i++;
            j++;
        }else{
            j=next[j];
        }
    }
    if(j>=length(str)){
        return i-length(str);
    }else{
        return -1;
    }
}
int main(){
    char txt[]="abaabc";
    char str[]="aa";
    int temp=KMP(txt,str);
    if(temp==-1){
        printf("Not found.\n");
    }else{
        printf("The first index = %d\n",temp);
    }
    return 0;
}