[C 예제] 보이어무어 간단버젼 - 동작예제 -
SoftWare/C / C++
Xeno's Life Blog (http://XenoStudy.tistory.com)
- 글쓴이 : Xeno
- 원본출처 : 본문에 없으면 직접작성.
- 기타사항 :
   * 틀린사항 및 문의사항은 댓글달아주세요.
   * 퍼가실땐 댓글달아주시고, 출처는 밝혀주세요.ㅎ



크리에이티브 커먼즈 라이선스
Creative Commons License

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

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


# include <limits.h>

# include <string.h>

# include <stdio.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 ) ;



저작자 표시
신고
Name
Password
Homepage
Secret

티스토리 툴바