07 - 보이어 . 무어법 (자바편)

🌏 주제 : 07 - 보이어 . 무어법 (자바편)

---

 

 

 

 

 

 

 

 

 

🌏 보이어 . 무어법 (자바편)

---

보이어-무어 알고리즘

KMP 알고리즘의 개선판이라고 할 수 있습니다. 시간복잡도는 최악의 경우 O(N)이지만 평균 O(N/M)의 시간복잡도를 가진다고 합니다. O(N+M)인 KMP 알고리즘보다 향상된 성능을 기대할 수 있습니다.

보이어-무어 알고리즘의 작동은 KMP 알고리즘과 유사하게 불필요한 비교는 건너뛰고 유의미한 비교만 진행하겠다는 것입니다. KMP 알고리즘의 경우에는 접두사와 접미사가 같은 최대길이를 저장하는 배열을 만들어 앞에서부터 검사를 진행하였다면, 보이어-무어 알고리즘은 문자열을 검색할때 주로 뒤에서 부터 확인합니다.

보이어-무어 알고리즘은 두가지 이동 방법이 존재하지만 주로 사용하는 bad match table 방법으로 작성해보겟습니다.

 

 

 

 

 

 

 

 

🌏 구현과정

---

 

 

구현과정

KMP 알고리즘과 같이 건너뛰는 경우를 저장하는 배열(skip_table)을 만들어야 합니다. 이때 배열은 본문 문자열이 비교 문자열에 존재하는지, 존재한다면 불일치 시 얼만큼 건너뛰는지를 판단하는 정보를 가지고 만들게 됩니다.

비교 문자열의 각 문자마다 건너뛰는 value 값을 가지는 skip_table이 만들어져야 합니다. value의 의미는 '문자열에 불일치가 일어나면 마지막 문자를 기준으로 skip_table의 value만큼 뒤로 이동시키겠다' 입니다. 각 문자의 value는 비교문자열 길이(length) - 문자열 index - 1 중 0을 제외한 최솟값으로 계산할 수 있습니다. 이외 모든 문자는 비교문자열의 길이(length)로 계산합니다.