자료 구조와 알고리즘
문자열 안에서 패턴을 찾는 BM법(보이어-무어 알고리즘)의 특징으로 올바른 것은?
- A패턴의 끝 문자부터 비교하며, 일치하지 않은 텍스트의 문자가 패턴에 포함되지 않는다는 등의 정보를 사용해 패턴을 한 번에 크게 이동시킨다
- B텍스트의 앞에서부터 한 문자씩 이동하면서, 매번 패턴의 처음부터 끝까지 모든 문자를 비교한다
- C텍스트와 패턴을 모두 정렬한 다음 이진 탐색으로 찾는다
정답과 해설 보기
정답: A. 패턴의 끝 문자부터 비교하며, 일치하지 않은 텍스트의 문자가 패턴에 포함되지 않는다는 등의 정보를 사용해 패턴을 한 번에 크게 이동시킨다
BM법은 패턴을 끝 문자부터 비교하고, 불일치가 된 텍스트의 문자가 패턴에 포함되지 않으면 패턴 전체를 그 문자 너머까지 이동시킬 수 있다는 식의 표를 미리 만들어 둡니다. 그래서 자연스러운 문장에서는 텍스트의 많은 문자를 비교하지 않고 건너뛸 수 있습니다. 텍스트의 길이를 n, 패턴의 길이를 m이라 하면, 한 문자씩 이동하며 모두 비교하는 단순한 방법은 최악 O(nm)이 걸립니다. KMP 알고리즘도 불일치 정보를 사용해 이동시키지만, 이쪽은 패턴의 앞에서부터 비교하며 최악에도 O(n + m)을 보장합니다.