보이어-무어 알고리즘

보이어-무어 알고리즘

Boyer-Moore string search algorithm
http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algorithm
http://www.cs.utexas.edu/users/moore/
http://bric.postech.ac.kr/cyberedu/seminar/ksh1/basicalgo2/sld003.htm

PatternMatching.pdf

1975년에 고안된 알고리즘으로, 텍스트 패턴 매칭에서는 KMP(Knuth-Pratt-Morris) 알고리즘과 함께 가장 빠른 매칭 알고리즘으로 알려져 있다. 텍스트 에디터와 같은 응용 분야에서 가장 널리 사용된다고 함. (아..그래서 자격증 시험에도 나오는건가??)

--------------- quote ---------------
기본 소요시간은 O(nm)이지만, 약간의 변형으로 O(m)이 되며,
실제적으로는 sublinear가 되는 알고리즘--------------- quote --------------- 


보이어-무어 알고리즘의 C 구현

#include <stdio.h>
#include <string.h>


char *search(char *, char *);
void table(char *);


int skip[256];


int main(void)
{
    static char text[] = "This is a pen. That is a pencil.";
    char *p, *key = "pen";


    table(key);
    p = search(text, key);
    while ( p != NULL ) {
        printf("%s\n", p);
        p = search(p + strlen(key), key);
    }


    return 0;
}


void table(char *key)    /* create skip table */
{
    int k, n;


    n = strlen(key);
    for ( k = 0; k <= 255; k++ )
        skip[k] = n;
    for ( k = 0; k < n-1; k++ )
        skip[key[k]] = n - 1 - k;
}


char *search(char *text, char *key)
{
    int m, n;
    char *p;


    m = strlen(text);
    n = strlen(key);


    p = text + n - 1;
    while ( p < text+m ) {
        if ( *p == key[n-1] ) {
            if ( strcmp(p-n+1, key, n) == 0)
                return p-n+1;
        }
        p = p + skip[*p];
    }


    return NULL;
}

소스코드 출처 : C언어로 배우는 알고리즘
http://www.hanb.co.kr/look.php?isbn=89-7914-305-2