[자바 Do It! 알고리즘]Chapter07 문자열 검색 (Boyer-Moore법)

Boyer-Moore법은 브루트-포스법을 개선한 KMP법보다 효율이 더 우수하기 때문에 실제로 문자열 검색에 널리 사용하는 알고리즘입니다.

​

[Boyer-Moore법]

1. 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을

옮길 크기를 정합니다.

2. 텍스트 안에서 패턴에 들어 있지 않은 문자를 찾으면 해당 위치까지의 문자는 건너뛸 수 있습니다.

​

3. 이렇게 패턴의 길이를 n이라고 하면 현재 검사하고 있는 텍스트의 문자 위치로부터 '다음에 검사할 패턴의 마지막

문자 위치'가 n만큼 떨어질 수 있도록 패턴을 옮기면 됩니다.

4. Boyer-Moore 알고리즘도 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표(건너뛰기 표)를 만들어야 합니다. 패턴문자열의 길이가 n일 때 옮길 크기는 아래와 같은 방법으로 결정합니다.

1) 패턴에 들어있지 않은 문자를 만난 경우

(1) 패턴을 옮길 크기는 n입니다.

2) 패턴에 들어 있는 문자를 만난 경우

(1) 마지막에 나오는 위치의 인덱스가 k이면 패턴을 옮길 크기는 n-k-1입니다.

(2) 같은 문자가 패턴 안에 중복해서 들어 있지 않다면 패턴을 옮길 크기는 n입니다.

​

​