KMP算法和朴素的匹配算法的关键区别就是解决了主串指针i的回溯，原理如下

设主串S[]和模式串T[],如比较到模式串的第j个字符。

当主串指针i和模式串指针j比较时 ，说明他们前面的所有字符都已经对应相等了。而

Next[j]＝k的定义是T1T2…Tk-1＝＝Tj-k+1Tj-k+2….Tj-1且k是最大了，没有更长的了。

所以Si和Tj比较失败时Si和Tk去比较。不可能有 这种匹配的成功，因为S2S3…..Si-1= =T2T3……Tj-1,而T2T3….Tj-1是不等于T1T2….Tj-2。除非next[j]=j-1;因为next定义的是最长的。所以任何挪动小于next[j]的串的匹配都是不能成功的。直到Tnext[j]和S[i]相比是才是最早有可能成功的。

Int KMP_Index(Sstring S,Sstring T,int pos)

{ 

    i=pos;j=1;

while(i<=S[0]&&j<=T[0])

{

If(j=0||S[i]=T[j])//j=0表示模式串已经退到起点了说明在这个位置彻底不可能了，

   {  ++i; ++j;  } //i必须下移,j回到1开始

Else j=next[j];

}

If(j>T[0])  return i-T[0];

Else  return 0;

}

求next[j]的方法和原理

设k=next[j];那么T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1;

  若Tj= =Tk,那么T1T2…Tk-1Tk= =Tj-k+1……Tj-2Tj-1Tj;

  所以 next[j+1]=k+1=next[j]+1;且T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1已经是  

最长的序列，所以k＋1也是next[j+1]最长的

  若Tj不等于Tk,那么就需要重找了。即…..Tj-1Tj ?,

  T1T2….

  所以next[j+1]首先＝k＝next[j]; 即…..Tj-1Tj ?,

  T1T2…Tk-1.

若不相等，则next[j+1]=next[k]; 即…..Tj-1Tj  ?,

T1T2….Tnext[k]-1

直到找到这样的序列，  即…..Tj-1Tj ?,

T1T2 ...To

那么，next[j+1]=next[next[j]]=next[next[next[j]]]…..=o+1; 

Void get_next(Sstring T,int next[])

{ 

i=1;   next[1]=0;   j=0;//i表示当前求的next

While(i

{  

if(j=0 | | T[i]=T[j]) 

{

   ++i; 

   ++j;

   next[i]=j;

}

Else j=next[j];

}

}

因为 next[ ] 在匹配过程中，若T[ j ]=T[ next[j] ];那么当 S[i]不等于T[j],

S[ i]肯定也不等于T[k= next[j] ];

 所以 S[i]应直接与T[next[k]]比较，而我们通过将next[j]修正 

  为nextval[j]=next[next[j]];这样能使比较更少。

Void  get_nextval(Sstring T,int nextval[])

{

   i=1;  nextval[1]=0; j=0;

   while(i

   {

   if(j=0 || T[i]= T[j])

{

  ++i;

  ++j;

  if(T[i]!=T[j]) 

nextval[i]=j;

  else

nextval[i]=next[j];

   }

else

  j=nextval[j];

}