自小弟我理解的KMP 算法 模式匹配

自我理解的KMP 算法 模式匹配

首先，KMP最重要的是next 函数的设计，下面是next函数的原理

纯手写，可跳过不看，网上有比较抽象的理论，但是比较难以理解

下面是代码部分，重点在于 get_next 函数体

//KMP模式匹配算法

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

#define SUBSTRING_LEN 50 //子串长度为50

int next[SUBSTRING_LEN] ;//

void get_next (char *t , int next[]);

int Index_KMP (char *s , char *t , int pos) ;//返回子串 t 在主串s中第pos 位置之后的数组下标，不存在返回-1；

int main (){


  char *s = "123456123123" ;

  char *t = "123" ;

  int index ;

  get_next(t,next) ;

  index = Index_KMP(s,t,7);

  printf("%d\n",index);

  return 0;
}

int Index_KMP (char *s , char *t , int pos){


    int s_l = strlen(s) ;
    int t_l = strlen(t) ;
    int i = pos ;
    int j = 0;
    while (i<s_l && j<t_l){

        if ( j==-1 || s[i]==t[j]){//如果子串不能向右继续滑动（j=-1），或者子串与主串在该位置上相等，则同时向右滑动

            i++;
            j++;

        }else{// 子串向右滑动，继续与主串比较
          j = next[j] ;
        }

    }
    if (j>=t_l)
        return i-t_l;
    else
        return -1;


}

void get_next (char *t , int next[]){

   int s_l = strlen (t) ;
   int i = 0 ;
   int j = -1 ;//相当于子串下标
   next[0]=-1;
   while ( i < s_l ){

     if ( j==-1 || t[i]==t[j] ){

        i++ ;
        j ++ ;
        next[i] = j ;

     }else{

           j = next[j] ;

     }

   }

}