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

32 scanf("%s", s2);
33 idx = bf_match(s1, s2); /* 텍스트(s1)에서 패턴(s2)을 브루트-포스법으로 검색합니다. */
34 if(idx == -1)
35 puts("텍스트에 패턴이 없습니다.");
36 else
37 printf("%d번째 문자부터 match합니다.\n", idx + 1);
38
39 return 0;
40 }

bf_match 함수는 텍스트(txt)에서 패턴(pat)을 검색하여 텍스트의 위치(인덱스)를 반환합니

다. 텍스트에 패턴이 여러 개 있는 경우에 가장 앞쪽에 위치한 텍스트의 인덱스를 반환합니
다. 검색에 실패하면 –1을 반환합니다. 텍스트(txt)를 스캔하기 위한 변수로 pt를 사용하고, 패
턴(pat)을 스캔하기 위한 변수로 pp를 사용합니다. 두 변수는 처음에 0으로 초기화하고 스캔
을 하거나 패턴을 옮길 때마다 업데이트합니다.

그림 8-11에서 ●은 변수 pt, ●은 변수 pp입니다.

연습 Q9 오른쪽처럼 브루트-포스법의 검색 과정을 자세히 출력하는 프로 0 ABABCDEFGHA
문제 그램을 작성하세요. 패턴을 옮길 때마다 검사하는 텍스트의 첫 번째 문 +
ABC
자 인덱스를 출력하고 검사 과정에서 비교하는 두 문자가 일치하면 +,
ABABCDEFGHA
다르면 |를 출력하세요. 마지막에는 비교한 횟수를 출력하세요. +
ABC
ABABCDEFGHA
Q10 bf_match 함수는 텍스트에 패턴이 여러 개 있으면 가장 앞쪽의 |
ABC
인덱스를 반환합니다. 이제는 가장 뒤쪽의 인덱스를 반환하는 bf_
matchr 함수를 작성해 보세요. 1 ABABCDEFGHA
|
ABC
int bf_matchr(const char txt[], const char pat[]); … 중략 …

비교를 7회 시도합니다.

08•문자열 검색 323