보이어-무어 알고리즘
부르트포스, KMP 알고리즘보다 향상된 알고리즘이며 더 자주 사용된다고 한다.
- 보이어-무어 알고리즘의 작동은 KMP 알고리즘과 유사하게 불필요한 비교는 건너뛰고 유의미한 비교만 진행하겠다.
알고리즘
- KMP 알고리즘의 개선이 된 알고리즘으로, 시간 복잡도는 최악의 경우 O(N) 평균적인 경우 O(N/M)입니다.
이전에 KMP 알고리즘이 O(N+M)이기 때문에 향상이 이루어졌습니다.
- KMP 알고리즘의 경우에는 접두사와 접미사가 같은 최대길이를 저장하는 배열을 만들어 앞에서부터 검사를 진행하였다면, 보이어-무어 알고리즘은 문자열을 검색할때 주로 뒤에서 부터 확인합니다.
- KMP 알고리즘과 같이 건너뛰는 경우를 저장하는 배열(skip_table)을 만들어야 합니다. 이때 배열은 본문 문자열이 비교 문자열에 존재하는지, 존재한다면 불일치 시 얼만큼 건너뛰는지를 판단하는 정보를 가지고 만들게 됩니다.
예시
- 마지막 문자열을 기준으로 SKIP Table이 만들어집니다.
- 뒤부터 값을 하나씩 비교하여 움직일 값을 설정하여 줍니다.
SKIP TABLE 예시1
SKIP TABLE 예시2
STEP1. S와 E에서 불일치 + S는 SKIP TABLE에 존재하지 않아 6칸 이동
STEP2. 마지막 N와 E를 비교하여 N이 SKIP TABLE에 있음으로 5칸 이동
탐색 완료