Pattern Matching Source Code

패킷 분석기를 짜다 패턴 매칭이 필요해서 찾아본 소스중 하나.

이 알고리즘과 KMP가 패턴매칭 알고리즘 중에서 가장 좋다는 군요.

// Boyer Moore 패턴 매칭 바이너리 버전

long Moore(char* pszStr1 , long nData1 ,char* pszStr2 , long nData2)

{

long i, j, k, len;

static int skip[UCHAR_MAX + 1];

unsigned char c, tail;



len = nData2;

if(len == 0) return -1;



tail = pszStr2[ len - 1 ];

if(len == 1 )

{

for(i=0; i != nData1; i++)

if( pszStr1[i] == tail ) return i;

}

else

{

for( i = 0; i <= UCHAR_MAX; i++)skip[i] = len;

for( i = 0; i< len -1 ; i++)

skip[ pszStr2[i]] = len - 1 - i;



while( c = pszStr1[i] , i != nData1 ){

if( c == tail ){

j = len - 1; k= i;

while( pszStr2[--j] == pszStr1[--k])

if( j == 0 ) return k;

}

i += skip[c];

}

}

return -1;

}

출처 : 데브파아