Boyer Moore 문자열 패턴 매칭

오후 4:03 2000-05-16
조경민
Boyer Moore
==================================================================

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;
}


=======================================================================


문자열 패턴 매칭
long Moore(char* pszStr1,char* pszStr2 )
{
        long i, j, k, len;
        static int skip[UCHAR_MAX + 1];
        unsigned char c, tail;

        len = strlen((char*)pszStr2 );
        if(len == 0) return -1;

        tail = pszStr2[ len - 1 ];
        if(len == 1 )
        {
                for(i=0; pszStr1 != '\0'; 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]) != '\0'){
                        if( c == tail ){
                                j = len - 1; k= i;
                                while( pszStr2[--j] == pszStr1[--k])
                                        if( j == 0 ) return k;
                        }
                        i += skip[c];
                }
        }
        return -1;
}