KMP算法实验

1．编程计算模式串（子串）的next值。

2．利用KMP算法在主串中找到模式串的位置。

 

参考代码：

---------

int getNexlVal( char * s,  int j)//求字符串S的j的模式值

{

 if( j == 1) return 0;//j=1，next[j]=0

 

 int max = 0;//其他情况，next[j]=max+1=1

 for( int l = 1; l < j-1 ; l ++ )//从K前面第l个数开始找

 {

  for( int k = 1; k <=l; k ++)//k代表从字符串开始的l的前面的数遍历

  {

   if( s[k] != s[j-l+k-1] ) break;//字符串从头开始的第k个值与第j个数前的第l个值不相等，跳出

             

  }

  if(k == (l+1))//j前有l个数和从头开始的l个数相同，第l+1=k个数不同

  {

   if(max <l) max = l;//max=l

  }

//模式串s中下标为j的字符，如果j的前面k个

//字符与开头的k个字符相等，且T[j] != T[k]

 }

 return max+1;//next[j]=max+1=l+1=k

}

void getNext( char * s, int * val)

{

 printf("VAL%s:",s);

 for( int i = 1; i< strlen(s); i ++ )

 {

  val[i] = getNexlVal( s,  i);

  printf("%d ",val[i]);

 }

 printf("\n");

 return;

}

int KMP( char * r, char *s , int * v)

{

 int i = 1;

 int j = 1;

 while( i<strlen(r) && j<strlen(s))

 {

  if( j==0 || r[i] == s[j] ){ i++;  j++; }//继续比较后续字符

  else j = v[j];//模式串向右移动

 }

 if( j == strlen(s)) { printf("FOUND @ %d \n", i-j+1); return i-j;}//匹配成功

 else return 0;

}

 

int main(int argc, char* argv[])

{

 char s[10];

 char r[100];

 int next2[10];

 printf("子串：\n");

 scanf("%s",s);

 printf("主串：\n");

 scanf("%s",r);

 getNext(s,next2);

 KMP( r,s,next2);

 return 0;

}