posts - 206, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

KMP算法

Posted on 2006-10-21 20:27 魔のkyo 阅读(293) 评论(0)  编辑 收藏 引用 所属分类: Programming

 

#define  B_MAX_LEN 2000
int  next[B_MAX_LEN];

void  Compute_Next( char  B[]){
    
int  i;
    next[
0 ] = next[ 1 ] = 0 ;
    
for (i = 2 ;B[i];i ++ ){
        
int  j = next[i - 1 ];
        
while (B[i - 1 ] != B[j]  &&  j > 0 )
            j
= next[j];
        
if (B[i - 1 ] == B[j])
            next[i]
= j + 1 ;
        
else
            next[i]
= 0 ;
    }
}

// 串匹配的KMP算法
// 返回A中第一个与B匹配的子串的指针,若找不到则返回NULL
// 需要已经对串B计算好next[]
char *  String_Match( char  A[], char  B [])
{
    
int  i = 0 ,j = 0 ;
    
while (A[i]  &&  B[j]){
        
if (A[i] == B[j]){
            
++ i;
            
++ j;
        }
        
else  {
            
if (j == 0 ) ++ i;
            
else   if ( ! B[j]) break ;
            
else  j = next[j];
        }
    }
    
if ( ! B[j]) return   & A[i - j];
    
else   return  NULL;
}
只有注册用户登录后才能发表评论。