한양과기고 에듀테크 수업도구 대시보드

보이어–무어 문자열 검색 (Boyer–Moore)

KMP는 텍스트를 앞에서 뒤로 한 글자씩 훑는다. 보이어–무어는 발상을 뒤집는다 — 패턴을 텍스트에 겹쳐 놓고 맨 뒤 글자부터 왼쪽으로 비교한다. 불일치가 나면 그 위치의 텍스트 글자가 패턴에 아예 없거나 멀리 있을 때, 패턴을 한 칸이 아니라 여러 칸 껑충 건너뛴다. 그래서 실제로는 텍스트의 모든 글자를 보지도 않고 끝나는 경우가 많다 — 평균 O(n / m)에 가깝다. grep, 편집기의 "찾기", str.find 구현이 이 아이디어를 쓴다.

1. 나쁜 문자 규칙 (Bad Character Rule)

패턴의 각 글자가 패턴 안에서 가장 오른쪽에 나오는 위치를 미리 표로 만든다. 비교 중 텍스트의 글자 c에서 불일치가 나면, 패턴의 그 c가 텍스트의 c와 겹쳐지도록 패턴을 오른쪽으로 민다. 패턴에 c가 없으면 패턴 전체를 그 자리 다음으로 통째로 건너뛴다.

패턴 (pattern)

표에 없는 글자 = "가장 오른쪽 위치 -1" → 그 글자에서 불일치가 나면 패턴을 비교위치 + 1칸 만큼 크게 점프.

2. 탐색 시각화 — 뒤에서부터 비교, 불일치 시 껑충

텍스트 (text)

패턴 (pattern)

텍스트와 패턴을 입력하고 ▶ 한 단계를 눌러 시작하세요.

비교 횟수 (Boyer–Moore)

비교 횟수 (단순 탐색)

찾은 위치 수

주황 칸 = 지금 비교 중 · 초록 칸 = 뒤에서부터 일치한 꼬리 · 빨강 칸 = 불일치 · 회색 칸 = 껑충 뛰며 아예 안 본 텍스트 글자 · 분홍 = 패턴 발견. 건너뛴 칸이 많을수록 빠르다.

3. 좋은 접미사 규칙 (Good Suffix Rule)

이미 맞은 꼬리

뒤에서부터 비교하다 보면 일부 글자는 이미 일치한 뒤 불일치가 난다. 그 일치한 "꼬리(접미사)"가 패턴 앞쪽에 또 등장한다면, 거기로 정렬되게 민다.

꼬리가 없으면

일치한 꼬리가 패턴 다른 곳에 없으면, 그 꼬리의 접미사가 패턴의 접두사와 겹치는 최대 길이만큼만 남기고 민다.

두 규칙의 합체

실제 구현은 매 불일치마다 나쁜 문자 규칙과 좋은 접미사 규칙이 제안하는 이동량을 둘 중 더 큰 값으로 택한다. 절대 뒤로 가지 않으니 안전하다.

최악의 경우

두 규칙을 다 써도 "AAAA…"에서 패턴 "BAAA" 같은 입력은 O(n·m). Galil 규칙을 더하면 최악에도 O(n) 보장.

4. 파이썬 구현 (나쁜 문자 + 좋은 접미사)

# 나쁜 문자 표: 각 글자의 가장 오른쪽 위치 (없으면 -1)
def bad_char(p):
    last = {}
    for i, ch in enumerate(p):
        last[ch] = i          # 나중 값이 덮어쓰므로 = 가장 오른쪽
    return last

# 좋은 접미사 이동표 (경계 배열 이용) — O(m)
def good_suffix(p):
    m = len(p); shift = [0] * (m + 1); border = [0] * (m + 1)
    i, j = m, m + 1; border[i] = j
    while i > 0:
        while j <= m and p[i - 1] != p[j - 1]:
            if shift[j] == 0: shift[j] = j - i
            j = border[j]
        i -= 1; j -= 1; border[i] = j
    j = border[0]
    for i in range(m + 1):
        if shift[i] == 0: shift[i] = j
        if i == j: j = border[j]
    return shift

def boyer_moore(text, p):
    n, m = len(text), len(p)
    last = bad_char(p); gs = good_suffix(p)
    s = 0                                # 패턴이 놓인 시작 위치
    while s <= n - m:
        j = m - 1
        while j >= 0 and p[j] == text[s + j]:
            j -= 1                        # 뒤에서 앞으로
        if j < 0:
            yield s
            s += gs[0]
        else:
            bc = j - last.get(text[s + j], -1)   # 나쁜 문자 이동
            s += max(1, bc, gs[j + 1])       # 둘 중 큰 쪽으로 껑충

핵심 두 줄: while p[j] == text[s+j]: j -= 1 (뒤에서부터) 와 s += max(1, bc, gs[j+1]) (한 번에 크게 점프).