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

보이어-무어 (Boyer-Moore)

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

01 Explore How It Works

Interactive Step-by-Step
Boyer-Moore · "ABC"
text
A
B
A
A
A
B
C
D
A
B
C
pattern

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

Logic Node1 / 7

02 Understand It Simply

For Everyone
🔑Analogy

끝 글자부터 맞춰보고 안 맞으면 성큼성큼 건너뛰는 찾기와 같습니다.

💡In Plain Words

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

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

📍Where It's Used
  • –텍스트 편집기 찾기·바꾸기
  • –grep
  • –대용량 검색

03 Python Implementation

A clean, readable reference implementation of the core logic of 보이어-무어 (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 Frequently Asked Questions

FAQ
What is 보이어-무어 (Boyer-Moore)?+

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

What is the time complexity of 보이어-무어 (Boyer-Moore)?+

The time complexity of 보이어-무어 (Boyer-Moore) is 최선 O(n / m). Follow the step-by-step visualization to see exactly why.

Where is 보이어-무어 (Boyer-Moore) used?+

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

What's a simple analogy for 보이어-무어 (Boyer-Moore)?+

끝 글자부터 맞춰보고 안 맞으면 성큼성큼 건너뛰는 찾기와 같습니다.

→ Strings — see allRelated
🔤KMP 문자열 탐색 (Knuth-Morris-Pratt)
O(n + m)
🔤라빈-카프 (Rabin-Karp)
평균 O(n + m)
Guide Progress0%