Boyer-Moore 알고리즘

Boyer-Moore 알고리즘

패턴의 끝에서부터 비교하며 불일치 시 나쁜 문자 규칙과 좋은 접미사 규칙을 활용하여 많은 문자를 건너뛰는 효율적인 문자열 매칭 알고리즘

목적: 빠른 문자열 검색, 실용적 성능, 대규모 텍스트 처리

특징: 오른쪽에서 왼쪽 비교, 큰 폭 이동, 전처리 필요, 평균 빠름

핵심 규칙

• •나쁜 문자 규칙(Bad Character): 불일치 문자가 패턴에 있으면 정렬, 없으면 패턴 길이만큼 이동
• •좋은 접미사 규칙(Good Suffix): 일치한 접미사를 활용하여 이동 거리 결정

동작: ① 패턴을 텍스트 시작에 정렬 → ② 패턴 끝에서부터 비교 → ③ 불일치 시 두 규칙 중 큰 이동 선택 → ④ 반복

전처리: 나쁜 문자 테이블(O(m+σ), σ=알파벳 크기), 좋은 접미사 테이블(O(m))

시간 복잡도: 최선 O(n/m) - 많이 건너뜀, 평균 O(n), 최악 O(nm) - 전처리 포함 O(n+m) 개선 가능

공간 복잡도: O(m + σ)

장점: 평균 매우 빠름, 큰 알파벳에서 효율적, 실용적, 오른쪽 비교로 조기 탈출

단점: 전처리 복잡, 작은 패턴에서 오버헤드, 최악 케이스 느림

적용사례: grep, 텍스트 에디터, 검색 엔진, 바이러스 스캐너, 생물정보학

비교: Boyer-Moore(평균빠름/복잡) vs KMP(O(n+m)보장/단순) vs Rabin-Karp(해시/다중패턴)

연관: 문자열 매칭, KMP, 패턴 검색, 전처리