Page 331 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５
A B C X D E Z C A B A C A B A C
A B A C
모든 문자가 일치합니다.
[그림 8-17] 검색에 성공한 경우

그런데 Boyer-Moore 알고리즘도 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표

(건너뛰기 표)를 미리 만들어야 합니다. 패턴 문자열의 길이가 n일 때 옮길 크기는 아래와 같은
방법으로 결정합니다. 건너뛰기 표는 KMP법에서 이미 작성해 보았습니다.

패턴에 들어 있지 않은 문자를 만난 경우
1. 패턴을 옮길 크기는 n입니다. 그림 8-13을 다시 예로 들어 살펴보면 'X'는 패턴에 들어 있지 않으므로 4만
큼 옮깁니다.

패턴에 들어 있는 문자를 만난 경우
1. 마지막에 나오는 위치의 인덱스가 k이면 패턴을 옮길 크기는 n – k – 1입니다. 그림 8-16을 다시 예로 들면
'A'는 패턴의 두 곳에 들어 있지만 마지막 인덱스를 기준으로 하여 패턴을 1만큼(4-2-1) 옮깁니다.
2. 같은 문자가 패턴 안에 중복해서 들어 있지 않다면("ABAC"의 'C'는 패턴 안에 1개만 들어 있습니다) 패
턴을 옮길 크기는 n입니다.

위의 규칙에 의해 만든 건너뛰기 표를 그림 8-18에 나타냈습니다.

이 그림에 표시된 옮길 크기는 대문자뿐입니다. 이 표에 없는 문자(숫자나 기호 등)의 옮길 크기는 모두 4입니다.
텍스트 … "ABCXDEZCABACABAC" 패턴 … "ABAC"

A B C D E F G H I J K L M
1 2 4 4 4 4 4 4 4 4 4 4 4

N O P Q R S T U V W X Y Z
4 4 4 4 4 4 4 4 4 4 4 4 4

[그림 8-18] Boyer-Moore법을 사용해 만든 건너뛰기 표

실습 8-14는 Boyer-Moore법을 사용한 프로그램입니다. 이때 패턴에 존재할 수 있는 모든
문자의 옮길 크기를 계산하고 저장해야 하기 때문에 건너뛰기 표의 요소 개수는 UCHAR_
MAX + 1입니다.

UCHAR_MAX는 표현할 수 있는 문자의 개수를 의미하며 <limits.h> 안에 객체 형식 매크로로 정의되어 있습니다. 자료
형은 unsigned char형입니다.
여기서 설명한 하나의 배열만 사용해서 검사하는 방법은 간단하게 구현한 Boyer-Moore 알고리즘입니다. 원래의 Boyer-
Moore법은 2개의 배열로 문자열을 검사합니다.

08•문자열 검색 331