Notice
suyeonme
[Algorithm/문자열 탐색] 보이어-무어(Boyer-Moore) 알고리즘 본문
1. 보이어-무어(Boyer-Moore) 알고리즘이란?
- 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하며 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정하는 알고리즘이다.
- 시간 복잡도는 O(n/m)으로 매우 빠르다.(n은 텍스트의 길이, m은 패턴의 길이)
2. 동작 방식
문자열 탐색은 패턴의 맨 마지막 글자부터 시작한다.
2.1 Bad Character
- 패턴의 현재 문자와 일치하지 않는 텍스트의 문자 (패턴: 찾을 문자열, 텍스트: 탐색을 수행할 문자열)
- Bad Character가 패턴에 존재하는 경우와 패턴에 존재하지 않는 경우를 나누어 접근한다.
Bad Character가 패턴에 존재하는 경우
- 인덱스 2에서 불일치 발생 (C는 bad character)
- C는 패턴에 존재한다.
- 패턴에서 가장 나중에 있는 C의 위치를 현재 패턴의 텍스트 위치로 이동한다.
T G C G A C E B
A C E
A C E
Bad Character가 패턴에 존재하지 않는 경우
- 인덱스 2에서 불일치 발생 (B는 bad character)
- B는 패턴에 존재하지 않는다.
- 따라서 패턴의 위치를 인덱스 3으로 이동한다.
T G B G A C E B
A C E
A C E
3. 구현하기
static int bmMatch(String text, String pattern) {
int pt; // text 커서
int pp; // pattern 커서
int textLen = text.length();
int patLen = pattern.length();
int[] skip = new int[Character.MAX_VALUE + 1]; // 건너뛰기 표
// 건너뛰기 표 생성
for(pt = 0; pt <= Character.MAX_VALUE; pt++) {
skip[pt] = patLen;
}
for(pt = 0; pt < patLen - 1; pt++) {
skip[pat.charAt(pt)] = patLen - pt - 1;
}
// 문자열 검색
while(pt < textLen) {
pp = patLen - 1;
while(text.charAt(pt) == pat.charAt(pp)) {
if(pp == 00) {
return pt;
}
pp--;
pt--;
}
pt += (skip[text.charAt(pt)] > patLen - pp) ? skip[text.charAt(pt)] : patLen - pp;
}
// 검색 실패
return -1;
}
'프로그래밍👩🏻💻 > 알고리즘' 카테고리의 다른 글
[알고리즘] 탐욕 알고리즘(Greedy Algorithm) (0) | 2022.07.25 |
---|---|
[Algorithm/문자열 탐색] KMP(Knuth–Morris–Pratt) 알고리즘 (0) | 2022.06.28 |
[Algorithm/문자열 탐색] 브루트-포스법(Brute force method) (0) | 2022.06.27 |
[Algorithm] 도수/계수 정렬(Counting Sort) (0) | 2022.06.26 |
[Algorithm] 힙 정렬(Heap Sort) (0) | 2022.06.26 |
Comments