KMP实现

kmp next数组 理解

#include <stdio.h>
#include <string.h>

void kmp_next(char* s,int* next){
  int i=0;
  next[0]=-1;
  int k=-1;
   while(i<strlen(s)){
    printf("j=%d  K=%d \n",i,k);

    if(k==-1 || s[i]==s[k]){
        i++;
        k++;
        next[i]=k;

    }else{
        k=next[k];
    }
   }

   printf("------------------------------\n");
    i=0;
   while(i<strlen(s)){
    printf(" %c |" ,s[i]);
    i++;
   }
   printf("\n");

    i=0;
   while(i<strlen(s)){
    printf(" %d |" ,next[i]);
    i++;
   }
   printf("\n");
   printf("------------------------------\n");

}



int  kmp_search(char* s, char * t ,int i){
    int slen=strlen(s);
    int tlen=strlen(t);
    int j=0;
    int* arr;
    arr=malloc(tlen*sizeof(int));
    kmp_next(&t[0],arr);


    while(i<=slen){
           printf("%c %c \n",s[i-1],t[j]);
        if(s[i-1]==t[j]){
            j++;
            i++;
        }else{
            j=arr[j];
            if(j==-1){
                i++;
                j=0;
            }
        }

        if(j==tlen){
            return i-j;
        }

    }

    return  0;
}