보이어 무어(boyer moore) 알고리즘

string = 'here is a simple example'

pattern = 'example'

 

BM의 특징은 패턴의 마지막 글자부터 비교를 한다는 것이다.

다른 한가지는 initialize를 한다는것이다.

 

여기서 말하는 초기화란 다음과 같다.

 

우선 영어의 경우 1바이트로 표현하기 때문에 1바이트가 가질수 있는 최대 크기는 256이다.

따라서

256개의 interger 배열을 선언하고 배열안에는 패턴의 길이로 초기화를 한다.

'example'의 경우는 7로 초기화를 한다.

 

그리고 'example'의 각 글자에 해당하는 알파벳에는 다른알파벳과 다른 숫자로 초기화를 한다.

 

초기화할 배열을 arr로 하면

arr[e] = 6

arr[x] = 5

arr[a] = 4

arr[m] = 3

arr[p] = 2

arr[l] = 1

 

이배열의 의미는 비교하다가 패턴과 스트링의 값이 다를때 이동할 거리를 말한다.

 

 

H E R E    I  S   A    S I M P L E   E X A M P L E

E X A M PL E

 

S != E

arr[S] = 7 ('s' 다른 대부분의 알파벳과 마찬가지로 example의 길이로 초기화 되었다)

 

 

따라서 EXAMPLE는 7만큼 이동한다.

 

H E R E    I  S    A    S  I  M  P L E   E X A M P L E

                     E X A M P L  E

 

 

 

 

 

 

문자열 패턴 매칭

#include
#include
#include
#define INDEX_SIZE 1024

long bm(unsigned char* str1,unsigned char* str2 )
{
    int i;
    int j;
    int k;
    int size1;
    int size2;
    static int index[INDEX_SIZE];
    unsigned char ch, tail;

    size1 = strlen((char*)str1 );
    size2 = strlen((char*)str2 );

    if(size1 == 0 || size2 == 0)  return -1;

    tail = str2[ size2 - 1 ];

    switch(size2)
    {
        case 1:
            for( i = 0; str1 != '\0'; i++)
            {
                if( str1[i] == tail )
                    return i;
            }
            break;
        default:
            for( i = 0; i < index_SIZE; i++) index[i] = size2;

            for( i = 0; i < size2 - 1 ; i++)        index[str2[i]] = size2 - 1 - i;

            while( ( ch = str1[i]) != '\0' )
            {
                if( ch == tail )
                {
                    j = size2 - 1;
                    k = i;
                    if(k > size1)   break;
                    while( str2[--j] == str1[--k] )                                                                                                                                                                                                               {
                        if( j == 0 )                                                                                                                                                                                                                                      return k;
                    }
                }
                i += index[ch];
            }
            break;

    }
    return -1;
}        

int     main()
{

    int   ret;
    //    char    *str1 = "HERE IS A SIMPLE EXAMPLE";
    //    char    *str2 = "EXAMPLE";
    int   size;
    char  *str1 = "수리 영역, 언어 영역, 사회탐구 영역중에서 가장 어려운건 수리 영역이다";
    char  *str2 = "영역";
    char  *pstr;
    size = strlen(str2);

    pstr = str1;
    while(1)
    {
        ret = bm(pstr,str2);
        if(ret == -1)       break;
        printf("%s\n",pstr+ret);
        pstr += (ret + size);
    }

}