[C code] 보이어-무어 알고리즘 (Boyer-Moore Algorithm)

앞서, 아래 PDF가 이해하기 쉽게 잘 나와있음

http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf

 

보이어-무어 알고리즘 Boyer-Moore Algorithm

대부분의 워드 검색 기능에서 채택되어 사용되는 알고리즘

​

나쁜 문자 이동 (Bad Character Method)와 착한 접미부 이동 (Good Suffix Method) 의 방법이 있음

본 게시글은 나쁜 문자 이동 방법을 다룸

​

나쁜 문자 이동

1) 나쁜 문자 발견

2) 패턴의 나쁜 문자와 본문 문자열의 나쁜 문자 위치를 일치하도록 패턴 이동

+) 불가한 경우 -> 문자열의 나쁜 문자 위치보다 패턴의 나쁜 문자 위치가 뒤쪽인 경우

-> 착한 접미부 이동 방식 이용 or 1 이동

​

패턴의 오른쪽부터 비교하여 텍스트 문자를 모두 비교하지 않아도 탐색이 가능 -> O(n/m)

최악 -> O(nm) ex) AAAAAAA / AAA

 

Txt 문자열에 점선 박스에 있는 문자를 검사하지 않음 / 화살표 되어있는 8개의 문자를 스킵함

위 사진의 화살표가 나타내듯이 나쁜 문자를 이용하여 스킵해가며 문자열을 검색함

 

---

 

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

int Max(int a, int b)
{
    if(a > b)
        return a;
    else
        return b;
}

// 나쁜 문자를 이용한 보이어-무어 알고리즘
int BoyerMooreSearch(char *txt, char *pat)
{
    int lengTxt = strlen(txt);
    int lengPat = strlen(pat);

    int badchar[256] = { -1, };     // 모든 배열을 -1로 초기화한다
    for(int i=0 ; i<lengPat ; i++)
        badchar[(int)pat[i]] = i;   // 값을 채운다

    int s = 0, j;                   // s는 text에 대한 pattern의 이동값
    while(s < lengTxt-lengPat)
    {
        j = lengPat-1;

        while(j >= 0 && txt[s+j] == pat[j])
            j--;                    // pattern의 문자와 text가 매칭하면 j를 줄여
                                    // 나쁜 문자를 찾는다

        if(j < 0)                   // 문자열이 일치하였을 때
        {
            printf("문자열이 검색된 index : %d\n", s);
            s += (s<lengTxt-lengPat)? lengPat-badchar[(int)txt[s+lengPat]] : 1;
        }
        else
        {
            s += Max(1, j-badchar[(int)txt[s+j]]);
        }
    }
}

int main(void)
{
    char txt[] = "GCTTCTGCTACCTTTTGCGCGCGCGCGGAA";
    char pat[] = "CCTTTTGC";

    BoyerMooreSearch(txt, pat); //문자열이 검색된 index : 10

    return 0;
}

 

---

lengTxt = 30

lengPat = 8

​

badchar[256] -> -1 초기화

[int C] = 7

[int T] = 5

[int G] = 6

​

j<0이면, (맞음)

s<n-m이면,

( 패턴 바로 뒤의 인덱스를 나쁜문자로 형성 (badchar[txt[s+m]]) )

( 전체 m값에서 badchar값 가기 )

s += m-badchar[txt[s+m]]

s = n-m 이면, s += 1

​

j>0이면, (다름)

( 다른 문자의 인덱스를 나쁜문자로 형성 (badchar[txt[s+j]]) )

( 다른 값에서 badchar값 가기 )

s += j-badchar[txt[s+j]] 와 1 중 큰 값

​

---->

문자열이 검색된 index : 10

 

---

​

이 이외의 문자열 검색 알고리즘에는 라빈-카프 알고리즘, KMP 알고리즘 등이 있음

snupi.tistory.com/88

[Python] KMP 알고리즘 (문자열 검색 알고리즘)

 

- GeeksforGeeks

- 그리타GRITA