改进的KMP字符串查找算法

 

#include <stdio.h>
#include "string.h"
//得到子串T的j每次回退的值
void get_nextn(const char *T, int *nextn)
{
    int i,j;
    int len;
    i=1;
    j=0;
    nextn[1]=0; // 给出初始值
    len=strlen(T);
    while(i<len)
    {
     if(j==0||T[i]==T[j])
     {
         ++i;
         ++j;
         if(T[i]!=T[j])
             nextn[i]=j;
         else
             nextn[i]=nextn[j]; //KMP算法改进的部分
     }
     else
       j=nextn[j];
   }
}
int Index_KMP(const char *S,const char *T,int pos)
{
 int i=pos;
 int j=1;
 int lenS,lenT;
 int next[255];
 get_nextn(T,next);
 lenS=strlen(S);
 lenT=strlen(T);
 while(j<=lenT&&i<=lenS)
 {
  if(0==j||S[i]==T[j-1]) //字符串数组下表是从0开始的

  {
   ++i;
   ++j;
  }
  else{
   j=next[j];
  }
 }
 if(j>lenT)
 {
   return i-lenT;
 }
    else
    {
  return 0;
    }
}
int main()
{
 char *S="ijkabmndeddfdf";
 char *T="abmn";
 int pos=2;
 int revalue;
 revalue=Index_KMP(S,T,pos);
 printf("%d\n",revalue);
}