Boyer-Moore Algorithm

CorinBeom·2025년 4월 14일

Algorithm

목록 보기

13/15

⚡ Boyer-Moore 문자열 탐색 알고리즘 정리

Boyer-Moore 알고리즘은 가장 빠른 문자열 검색 알고리즘 중 하나로,
오른쪽에서부터 비교하고, 불일치 시 멀리 점프하는 방식으로 작동한다.
KMP보다 실전에서 평균 속도가 더 빠르며, 실제 검색기에도 많이 사용된다.

💡 핵심 아이디어

비교는 패턴의 오른쪽부터 시작
매칭 실패 시, 두 가지 규칙 중 더 멀리 뛸 수 있는 쪽을 선택해서 점프

🔑 두 가지 점프 전략

전략 이름	설명
Bad Character Rule	틀린 문자가 패턴 내 어디 있는지 보고, 그 문자 위치까지 점프
Good Suffix Rule	이미 일치한 접미사를 기준으로 점프 위치 결정

둘 중 더 긴 점프를 할 수 있는 쪽을 선택해서 이동

🔍 Bad Character Rule 예시

패턴: ABCD
텍스트: ABX...

D vs X 비교 → mismatch
X는 패턴 내에 없음 → 패턴 전체 길이만큼 점프 가능

→ 이게 Boyer-Moore의 스피드 핵심

🧠 알고리즘 흐름

전처리
- Bad Character 테이블 생성 (O(M))
- Good Suffix 테이블 생성 (O(M))
탐색
- 오른쪽에서부터 문자 비교
- mismatch 발생 시 → 두 규칙 중 긴 거리 점프

⏱ 시간복잡도

상황	시간복잡도
평균	O(N / M) → 실전에서 매우 빠름
최악	O(N × M) → 반복적인 텍스트/패턴일 경우

N: 텍스트 길이
M: 패턴 길이

최악은 느릴 수 있지만, 실전 성능은 거의 탑티어

🧪 실무 적용 예시

텍스트 편집기(Visual Studio Code, Sublime 등)
리눅스 grep
검색엔진 내부 문자열 필터
DB LIKE 연산 성능 최적화
브라우저 검색 기능(Ctrl + F)

✅ Boyer-Moore 코드 예제 (C 언어 기준)

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

#define NO_OF_CHARS 256

// Bad character 테이블 생성
void badCharHeuristic(char *str, int size, int badchar[NO_OF_CHARS]) {
    for (int i = 0; i < NO_OF_CHARS; i++)
        badchar[i] = -1;

    for (int i = 0; i < size; i++)
        badchar[(int) str[i]] = i;
}

// BM 검색 함수
void search(char *txt, char *pat) {
    int m = strlen(pat);
    int n = strlen(txt);

    int badchar[NO_OF_CHARS];
    badCharHeuristic(pat, m, badchar);

    int s = 0; // shift
    while (s <= (n - m)) {
        int j = m - 1;

        // 오른쪽부터 비교
        while (j >= 0 && pat[j] == txt[s + j])
            j--;

        if (j < 0) {
            printf("패턴 발견 위치: %d\n", s);
            s += (s + m < n) ? m - badchar[txt[s + m]] : 1;
        } else {
            int shift = j - badchar[(int) txt[s + j]];
            s += (shift > 1) ? shift : 1;
        }
    }
}

🔍 사용 예시

int main() {
    char txt[] = "ABAAABCD";
    char pat[] = "ABC";
    search(txt, pat);
    return 0;
}

KMP vs Boyer-Moore 요약 비교

항목	KMP	Boyer-Moore
비교 방향	왼쪽 → 오른쪽	오른쪽 → 왼쪽
점프 방식	LPS 기반	Bad Character + Good Suffix
평균 속도	안정적	훨씬 빠름
최악 시간복잡도	O(N + M)	O(N × M)
실무 활용도	중상	최상 (grep, 에디터 등)