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

브루트-포스법
이 알고리즘의 시간 복잡도는 O(mn)이지만 일부러 꾸민 패턴이 아니라면 시간 복잡도는 O(n)으로

된다고 알려져 있습니다. 단순한 알고리즘이지만 실제는 아주 빠르게 동작합니다.

KMP법
이 알고리즘의 시간 복잡도는 가장 나쁜 경우에도 O(n)입니다. 다만 처리가 복잡하고 패턴 안에 반복
이 없으면 효율이 좋지 않습니다. 그러나 검색 과정에서 검사하는 위치를 앞으로 되돌릴 필요가 없다는
특징이 있어 순서 파일을 읽어 들이며 검색할 때 많이 사용합니다.

Boyer-Moore법
이 알고리즘의 시간 복잡도는 가장 나쁜 경우라도 O(n)이고 평균적으로 O(n/m)입니다. 앞에서는 배
열을 1개만 사용하여 알고리즘을 구현했지만 2개의 배열을 사용하면 KMP법과 마찬가지로 배열을 만
드는 데 복잡한 처리가 필요하므로 효과가 떨어집니다. 1개의 배열을 사용하는 방법으로 간단하게 구
현한 Boyer-Moore법을 사용해도 충분히 빠릅니다.

이 알고리즘 가운데 가장 실용적인 문자열 검색 알고리즘은 간단하게 구현한 Boyer-Moore법이고
경우에 따라 브루트-포스법을 사용하기도 합니다.

실습 8-15는 strstr 함수를 사용하여 문자열을 검색하는 프로그램입니다.

실습 8-15 •완성 파일 chap08/strstr_test.c

01 /* strstr 함수를 사용한 프로그램 */
실행 결과
02 #include <stdio.h>
strstr 함수
03 #include <string.h>
텍스트 : ABABCDEFGHA
04 패턴 : ABC
05 int main (void) ABABCDEFGHA
06 { |
07 char s1[256], s2[256]; ABC
08 char *p;
09 puts("strstr 함수");
10 printf("텍스트 : ");
11 scanf("%s", s1);
12 printf("패턴 : ");
13 scanf("%s", s2);
14 p = strstr(s1, s2); /* 문자열 s1에서 문자열 s2를 검색 */

334 C 알고리즘