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

실습 8-14 •완성 파일 chap08/bm_match.c
01 /* Boyer-Moore법으로 문자열을 검색하는 프로그램 */
실행 결과
02 #include <stdio.h>
Boyer-Moore법
03 #include <string.h>
텍스트 : ABABCDEFGHA
04 #include <limits.h> 패턴 : ABC
05 3번째 문자부터 match합니다.
06 /*--- Boyer-Moore법으로 문자열을 검색하는 함수 ---*/
07 int bm_match (const char txt[], const char pat[])
08 {
09 int pt; /* txt 커서 */
10 int pp; /* pat 커서 */
11 int txt_len = strlen(txt); /* txt 문자 개수 */
12 int pat_len = strlen(pat); /* pat 문자 개수 */
13 int skip[UCHAR_MAX + 1]; /* 건너뛰기 표 */
14 for(pt = 0; pt <= UCHAR_MAX; pt++) /* 건너뛰기 표 만들기 */
15 skip[pt] = pat_len;
16 for(pt = 0; pt < pat_len – 1; pt++)
17 skip[pat[pt]] = pat_len - pt - 1;
18 /* pt == pat_len - 1 */
19 while(pt < txt_len) {
20 pp = pat_len – 1; /* pat의 마지막 문자부터 검사 */
21 while(txt[pt] == pat[pp]) {
22 if(pp == 0)
23 return pt;
24 pp--;
25 pt--;
26 }
27 pt += (skip[txt[pt]] > pat_len – pp) ? skip[txt[pt]] : pat_len – pp;
28 }
29 return -1;
30 }
31
32 int main (void)
33 {
34 int idx;
35 char s1[256]; /* 텍스트 */
36 char s2[256]; /* 패턴 */
37 puts("Boyer-Moore법");
38 printf("텍스트 : ");
39 scanf("%s", s1);
40 printf("패턴 : ");

332 C 알고리즘