BM 검색 알고리즘

BM 검색 알고리즘이란?

문자열을 데이터에서 검색할 때,

검색할 문자열의 끝에서부터 비교하다가

일치하지 않는 문자를 만나면 검색할 문자열만큼 이동하여 검색을 수행하는 알고리즘.

고안자인 Boyer-Moore 법이라고도 한다.

 

- 찾고자 하는 문자열이 중복되지 않을 경우

예를 들어 다음과 같은 데이터에서 'MYBK' 처럼 중복되지 않는 문자열을 찾을 경우.

M

Y

B

B

A

G

M

Y

B

K

찾고자 하는 문자열인 'MYBK'의 마지막 문자 'K'와 배열의 4번째 데이터, 배열[3] 데이터인 'B'를 비교한다.

서로 다르므로 4칸을 건너뛰고 검색한다.

 

- 찾고자 하는 문자열이 중복되는 경우

예를 들어 다음과 같은 데이터에서 'MBMBC' 처럼 중복되는 문자열을 찾을 경우.

M

B

M

B

M

B

C

K

A

B

M

B

M

C

M

B

A

B

C

A

찾고자 하는 문자열인 'MBMBC'의 마지막 문자 'C'와 배열의 5번째 데이터, 배열[4] 데이터인 'M'를 비교한다.

서로 다르므로 중복되는 'MB'만큼 2칸을 건너뛰고 검색한다.