Rabin-Karp算法不懂丫

lirongwei 发布于 2012/08/14 13:42
阅读 722
收藏 1

【开源中国 APP 全新上线】“动弹” 回归、集成大模型对话、畅读技术报告”

Rabin-Karp算法。

对于Rabin-Karp算法中得有一步我不是很理解,求教。

#include <stdio.h>  
#include <math.h>  
#include <assert.h>  
#include <string.h>  
#include <stdlib.h>  
#define d 256// number of characters in the alphabet  
#define PRIME 127 //A prime number  
  
  
void RABIN_KARP_MATCHER( char *T, char *P, int q)  
{  
    assert( T && P && q > 0 );  
    int M = strlen( P );  
    int N = strlen( T );  
    int i, j;  
    int p = 0;//hash value for pattern  
    int t = 0;//hash value for txt  
    int h = 1;  
      
    //the value of h would be "pow( d, M - 1 ) % q "  
/*算法导论上描述的是 h = pow( d, m-1 ) % q, 
算法导论上很容易出现数据溢出。我看到网上有个博客这么写的。我不敢确定正确性。大伙儿看看*/    
    for( i = 0; i < M - 1; i++)  
        h = ( h * d ) % q;  
  
    for( i = 0; i < M; i++ )  
    {  
        p = ( d * p + P[i] ) % q;  
        t = ( d * t + T[i] ) % q;  
    }  
      
    //Slide the pattern over text one by one  
    for( i = 0; i <= N - M; i++)  
    {  
        if( p == t)  
        {  
            for( j = 0; j < M; j++)  
                if(T[i+j] != P[j])  
                    break;  
            if( j == M )  
                printf("Pattern occurs with shifts: %d\n", i);  
        }  
        //Caluate hash value for next window of test:Remove leading digit,  
        //add trailling digit  
        if( i < N - M )  
        {  
            t = ( d * ( t - T[i] * h ) + T[i + M] ) % q;  
            if( t < 0 )  
                t += q;//按照书上的伪代码会出现t为负的情况,则之后的计算就失败了。  
        }  
    }  
}     
  
int main(int argc, char* argv[])  
{  
    char txt[] = "GEEKS FOR GEEKS";  
    char pat[] = "GEEK";  
    RABIN_KARP_MATCHER( txt, pat, 127 );  
      
    return 0;  
}</span>  

加载中
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部