1. 개념

“불필요한 건 건너뛰면서 검색을 빠르게!”

보이어 무어란, 문자열 검색에 사용되는 알고리즘 (문자열에서 특정 패턴 찾기)

근데, 브루트 포스 & KMP보다 훨씬 더 빠르다!

시간복잡도 : 최악 - O(N) / 평균 - O(N/M)

(KMP와의 차이)

• skip 배열을 만들고, 문자열과 패턴을 비교한다는 건 동일하지만

→ 1) skip 배열 만드는 방식 (KMP는 접두사 접미사 비교, 보이어무어는 패턴 value 구하는 공식)

→ 2) 문자열 비교 방향 (KMP는 왼쪽 오른쪽, 보이어무어는 오른쪽 왼쪽)

2. 원리

“뒷 부분에서 불일치가 일어날 확률이 높다!”

1. 오른쪽 끝부터 비교한다.

2. 본문의 문자열과 패턴에서 불일치 하는 문자를 찾는다.

3. 일정 길이만큼 이동하여 비교를 계속한다.