[알고리즘] 보이어･무어법

보이어･무어 알고리즘(Boyer-Moor algorithm)

이 알고리즘은 이전글에서 설명한 KMP보다 효율적이며 실제 프로그램에서 많이 사용되는 알고리즘이다.
패턴의 오른쪽부터 텍스트와 비교하기에 모든 텍스트와 비교할 필요없이 탐색이 가능하다.

 

패턴과 텍스트를 비교할 때 텍스트의 가장 뒷부분부터 비교한다. 비교해서 같지않은 문자열의 위치에 따라 패턴을 n만큼 이동시킨다. KMP와 동일하게 LPS를 만들어줘서 패턴의 반복되는 값을 찾아 문자열 검색을 효율적으로 이뤄지게한다.

 

LPS 표의 각 자리의 값은 텍스트 인덱스의 위치마다 바뀐다. 어떤 기준으로 바뀔까?

 

LPS = 패턴의 길이 값을 가진 27개의 정수를 담고 있는 리스트(대문자 기준이기에 소문자는 정수 개수 추가 필요)

LSP[알파벳 인덱스] = 패턴의 길이 - 패턴의 현재 인덱스 - 1

이렇게 패턴에 나오는 알파벳의 값만 수정해준다.

LPS를 만들어 줬다면 아래와 같은 코드로 문자열 검색을 실시해준다.

텍스트와 패턴을 알맞게 배정해준 뒤에 계산해준다. 만일 일치하지않는 문자열 발견 시에 LPS를 통해 패턴을 얼마나 옮겨줄지 선택한다. 패턴과 일치하는 문자열을 찾으면 그에 해당하는 문자열의 첫 인덱스 값을 리턴해주며 찾지 못한다면 -1을 리턴해준다.

 

평균 시간복잡도: O(텍스트의 길이 / 패턴의 길이)

최악의 시간복잡도: O(텍스트의 길이)