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

08-2 브루트-포스법

이번에는 문자열에서 문자열을 검색하는 알고리즘인 브루트-포스법(brute force method)을
살펴보겠습니다.

문자열 검색이란?

이제는 본격적으로 문자열을 검색하는(string S T R I N G 문자열 원본(텍스트)
searching) 알고리즘에 대해 알아보겠습니다. 문 I N 검색할 문자열(패턴)
자열 검색이란 어떤 문자열 안에 다른 문자열이
해당 문자열 패턴(IN)을 문자열 원본(STRING)에서 검색합니다.
들어 있는지 조사하고 들어 있다면 그 위치를 찾 [그림 8-9] 문자열 검색
아내는 것을 말합니다.

예를 들어, 문자열 "STRING", "KING"에서는 "IN"을 검색하면 문자열 검색에 성공합니다. 하
지만 문자열 "QUEEN"에서 "IN"을 검색하면 문자열 검색에 실패합니다. 그러면 지금부터는

이해하기 쉽게 검색할 문자열을 패턴(pattern)이라 하고 문자열 원본을 텍스트(text)라고 하겠
습니다.

브루트-포스법
다음 그림 8-10은 텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트-포스법을 사용해
검색하는 순서를 간략하게 나타낸 그림입니다.

a 텍스트의 첫 문자 'A'부터 시작하는 3개의 문 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０
a A B A B C D E F G H A
자와 "ABC"가 일치하는지 검사합니다. 'A'와 'B' A B C
패턴의 3번째 문자가 다른 경우
는 일치하고 'C'는 다릅니다.

b 패턴을 1칸 뒤로 옮깁니다. 텍스트의 2번째 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０
b A B A B C D E F G H A
문자부터 3개의 문자가 일치하는지 조사합니다. A B C
패턴의 1번째 문자가 다른 경우
'A'와 'B'가 다릅니다.

320 C 알고리즘