/*  data:2007 -1 - 7 by:snowhill
 char *s="abcdefhighcbcccfghiabcdefghikl";
 char *T="cbcbc"; next[]的值应为:    -1,0,0,1,2
 如果char *T="cbccc";next[]的值应为: -1,0,0,1,1
 next[]的求法相当于T自身的一个模式匹配

 在KMP_Find()中 如果J的值大于T的长度则查找成功
  */
#include  " iostream.h "
int  length( char   * s)
{
  int  i = 0 ;
  while (s[i] != NULL)
 i ++ ;
  return  i;
}

void  get_next( char   * T, int   * next)
{
    int   i  =   0 , j  =- 1 ; 
   next[ 0 ]  =- 1 ;
      while  (i < length(T))
     {
           if (j ==- 1 || T[i] == T[j]) 
            {             
               ++  i;
               ++  j; 
              cout << " i= " << i << " j= " << j << endl;
              next[i] = j;              
             }
             else  j = next[j];
          } // end while    
   for ( int  l = 0 ;l < length(T);l ++ )
     cout << next[l] << " \t " ;
     
cout << endl;
}
//  KMP算法
void  KMP_Find( char   * s,  char   * T)
{
           int  i = 0 , j = 0 ,k = length(s);
          cout << " k= " << k << endl;
           int   * next = new   int [k];
          get_next(T,next);
           while  (i < k)
          {
               if  (j =- 1 || s[i]  ==  T[j]){  ++ i;  ++ j; }
               else  j  =  next[j];
          }
           if  (j >= length(T))  cout << " 查找完毕!未找到 " << endl;
           else   cout << " 查找成功! " ;
          
}
/*  原始查找算法  */
void  find( char   * s, char   * T)
{
  int  i = 0 ,j = 0 ,k = length(s);
  if (j < length(T) && i < k)
  {
   if (s[i] == T[j])
   {
   j ++ ;
   i ++ ;
   } 
   else  {i = i - j + 1 ;j = 0 ;} 
  }
   if (j = length(T) - 1 )
  cout << " find is sucess! " << endl;
   else  
  cout << " error! " << endl;
}
  /*  测试函数  */
void  main()
{
  char   * s = " abcdefhighcbcccfghiabcdefghikl " ;
  char   * T = " cbcbc " ;
 find(s,T);
 KMP_Find(s,T);
    
}

snowhill 2007-01-07 11:40 发表评论