Algorithm Guidecomplexity: 최선 O(n / m)

보이어-무어 (Boyer-Moore)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Boyer-Moore · "ABC"

text

pattern

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

Logic Node1 / 7

Live Python

1def boyer_moore(text, pattern):

2 n, m = len(text), len(pattern)

3 last = {ch: i for i, ch in enumerate(pattern)} # 나쁜 문자 표

4 s = 0

5 while s <= n - m:

6 j = m - 1

7 while j >= 0 and pattern[j] == text[s + j]:

8 j -= 1 # 오른쪽 → 왼쪽 비교

9 if j < 0:

10 return s # 매칭 성공

11 s += max(1, j - last.get(text[s + j], -1)) # 점프

12 return -1

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

Guide Progress0%