Oh My Algorithm
Algorithm Guidecomplexity: 최선 O(n / m)

보이어-무어 (Boyer-Moore)

패턴을 오른쪽 끝부터 비교하고, 불일치 시 나쁜 문자 규칙으로 패턴을 크게 점프시키는 탐색입니다. 텍스트의 많은 글자를 건너뛸 수 있어 실무에서 가장 빠른 단일 패턴 탐색 중 하나입니다.

01보이어-무어 (Boyer-Moore)

보이어-무어 시작. 패턴을 오른쪽 끝부터 비교하고, 불일치 시 '나쁜 문자' 규칙으로 크게 점프합니다.

offset 0 · 패턴의 끝 글자 C와 text[2]=A를 비교 — 불일치합니다.

불일치한 text의 글자 'A'는 패턴 0번에 있습니다. 그만큼 패턴을 오른쪽으로 2칸 점프시킵니다.

offset 2 · 다시 끝 글자 C와 text[4]=A를 비교 — 또 불일치. 같은 규칙으로 점프합니다.

offset 4 · 오른쪽부터 C=C, B=B, A=A가 모두 일치합니다.

패턴이 인덱스 4에서 완전히 일치합니다 — 발견!

불일치 한 번에 여러 칸을 건너뛰어, 텍스트의 많은 글자를 아예 보지 않습니다 — 최선 O(n/m).

text
A
B
A
A
A
B
C
D
A
B
C
pattern
1 / 7

02 쉽게 이해하기

For Everyone
🔑핵심 동작

패턴의 끝 글자부터 맞춰 보고, 어긋난 글자에 따라 한 번에 여러 칸을 건너뜁니다. 본문과 패턴이 길수록 유리합니다.

💡쉽게 말하면

패턴을 오른쪽 끝부터 비교하고, 불일치한 글자에 따라 패턴을 크게 점프시킵니다.

텍스트의 많은 글자를 아예 건너뛰어 실무에서 가장 빠른 편이에요.

📍어디에 쓰나
  • –텍스트 편집기 찾기·바꾸기
  • –grep
  • –대용량 검색

03 파이썬 구현 코드

보이어-무어 (Boyer-Moore)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py
def boyer_moore(text, pattern):
    n, m = len(text), len(pattern)
    last = {ch: i for i, ch in enumerate(pattern)}  # 나쁜 문자 표
    s = 0
    while s <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1
        if j < 0:
            return s                  # 매칭 성공
        s += max(1, j - last.get(text[s + j], -1))
    return -1

04 자주 묻는 질문

FAQ
보이어-무어 (Boyer-Moore)란 무엇인가요?+

패턴을 오른쪽 끝부터 비교하고, 불일치 시 나쁜 문자 규칙으로 패턴을 크게 점프시키는 탐색입니다. 텍스트의 많은 글자를 건너뛸 수 있어 실무에서 가장 빠른 단일 패턴 탐색 중 하나입니다.

보이어-무어 (Boyer-Moore)의 시간복잡도는 어떻게 되나요?+

보이어-무어 (Boyer-Moore)의 시간복잡도는 최선 O(n / m) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

보이어-무어 (Boyer-Moore)은(는) 어디에 사용하나요?+

텍스트 편집기 찾기·바꾸기, grep, 대용량 검색.

보이어-무어 (Boyer-Moore)를 쉽게 비유하면?+

패턴의 끝 글자부터 맞춰 보고, 어긋난 글자에 따라 한 번에 여러 칸을 건너뜁니다. 본문과 패턴이 길수록 유리합니다.

→ 문자열 전체 보기Related
🔤KMP 문자열 탐색 (Knuth-Morris-Pratt)
O(n + m)
🔤라빈-카프 (Rabin-Karp)
평균 O(n + m)