[C] 보이어무어 간단버젼 - 동작예제 -

보이어무어를 실제 임베디드 환경에서 사용할일이 생김...

그나마 제일간단하고 제일 코드량이 적으면서 잘돌아가는 소스를 인터넷에서 받아서 테스트완료한 버젼이다.

예제소스

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

#define NO_OF_CHARS 256

// A utility function to get maximum of two integers
static int max (int a, int b) { return (a > b)? a: b; }

// The preprocessing function for Boyer Moore's bad character heuristic
static void badCharHeuristic( char *str, int size, int badchar[NO_OF_CHARS])
{
    int i;

    // Initialize all occurrences as -1
    for (i = 0; i < NO_OF_CHARS; i++)
         badchar[i] = -1;

    // Fill the actual value of last occurrence of a character
    for (i = 0; i < size; i++)
         badchar[(int) str[i]] = i;
}

/* A pattern searching function that uses Bad Character Heuristic of
   Boyer Moore Algorithm */
static int search( const char *txt,  int n, const char *pat, int m)
{

    int badchar[NO_OF_CHARS];

    /* Fill the bad character array by calling the preprocessing
       function badCharHeuristic() for given pattern */
    badCharHeuristic(pat, m, badchar);

    int s = 0;  // s is shift of the pattern with respect to text
    while(s <= (n - m))
    {
        int j = m-1;

        /* Keep reducing index j of pattern while characters of
           pattern and text are matching at this shift s */
        while(j >= 0 && pat[j] == txt[s+j])
            j--;


        /* If the pattern is present at current shift, then index j
           will become -1 after the above loop */
        if (j < 0)
        {
            // printf("\n pattern occurs at shift = %d\r\n", s);
            // kksowrks : return char start index..
            return s;

            /* Shift the pattern so that the next character in text
               aligns with the last occurrence of it in pattern.
               The condition s+m < n is necessary for the case when
               pattern occurs at the end of text */
            s += (s+m < n)? m-badchar[txt[s+m]] : 1;

        }

        else
            /* Shift the pattern so that the bad character in text
               aligns with the last occurrence of it in pattern. The
               max function is used to make sure that we get a positive
               shift. We may get a negative shift if the last occurrence
               of bad character in pattern is on the right side of the
               current character. */
            s += max(1, j - badchar[txt[s+j]]);
    }

    return -1;

}

사용방법

search( target_buff, target_buff_len, pattern_buff, pattern_buff_len ) ;