수다닷컴

질문 제목 : 카프-라빈 알고리즘 코딩분석질문 요약 :밑쪽부분(진하게 되있는)hash, rehash 코딩 분석부탁드려요..질문 내용 :
#include karprabin.h
#include stdio.h
#include math.h
int karprabin(char* text, int textsize, int start, char* pattern, int patternsize )
{
int i = 0;
int j = 0;
int coefficient = pow( 2, patternsize - 1 );
int hashtext = hash( text, patternsize );
int hashpattern = hash( pattern, patternsize );
for ( i=start; i=textsize - patternsize; i++ )
{
hashtext = rehash( text, i, patternsize - 1, hashtext, coefficient);

if ( hashpattern == hashtext )
{
for ( j=0; jpatternsize; j++ )
{
if ( text[i+j] != pattern[j] )
break;
}
if ( j = patternsize )
return i;
}
}
return -1;
}
int hash( char* string, int size )
{
int i = 0;
int hashvalue = 0;
for ( i=0; isize; i++ )
{
hashvalue = string[i] + ( hashvalue * 2 );
}
return hashvalue;
}
int rehash( char* string, int start, int size, int hashprev, int coefficient ){
if ( start == 0 )
return hashprev;

return string[ start + size - 1] + ( (hashprev - coefficient * string [start-1] ) * 2 );
}

신청하기