7-2장 브루트 - 포스법

1. 문자열 검색 정의하기 

 

문자열 검색 (string searching)

- 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어있다면 그 위치를 찾아내는 것

 

패턴(pattern)

- 검색할 문자열

 

텍스트(text)

- 문자열 원본

 

 

2. 브루트-포스법으로 검색하기 

 

- 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고 다음 텍스트의 위치로 

1칸 이동한 다음 다시 패턴의 첫 번째 문자부터 검사하는 알고리즘

 

 

ex) "ABABCDEFGHA"에서 패턴 "ABC"를 브루트- 포스법을 사용하여 검색

 

- 텍스트의 첫 문자 'A'부터 시작하는 3개의 문자와 "ABC"가 일치하는지 검사 

- 'A'와 'B'는 일치하고 'C'는 다름

 

- 패턴을 1칸 뒤로 옮김

- 텍스트의 2번째 문자부터 3개의 문자가 일치하는지 조사

- 'A'와 'B'가 다름

 

- 패턴을 다시 1칸 뒤로 옮김

- 'A','B','C' 모두 일치 

 

- 브루트- 포스법으로 문자열을 검색하는 프로그램

#include <stdio.h> 

//브루트- 포스법으로 문자열을 검색하는 함수 
int bf_match(const char txt[], const char pat[]) 
{
	int pt = 0;
	int pp = 0;
	while(txt[pt]!='\0' && pat[pp]!='\0') {
		if(txt[pt] == pat[pp]) {
			pt++;
			pp++;
		}
		else {
			pt = pt -pp+1; //검사할 텍스트 위치를 1칸 뒤로 이동
			pp = 0; 
		}
	}
	if(pat[pp] == '\0') 
		return pt - pp;
	return -1; // 패턴의 끝부분이 텍스트의 끝부분을 벗어나면 검색에 실패  
}

int main()
{
	char s1[256]; //텍스트
	char s2[256]; //패턴
	puts("브루트-포스법 ");
	printf("텍스트:");
	scanf("%s",s1);
	printf("패턴:");
	scanf("%s",s2);
	
	int idx = bf_match(s1,s2); //텍스트(s1)에서 패턴(s2)을 브루트-포스법으로 검색 
	if(idx == -1) 
		puts("텍스트에 패턴이 없습니다.");
	else
		printf("%d번째 문자부터 match합니다.\n",idx+1);
		
	return 0;
 }

 

bf_match 함수

- 텍스트(txt)에서 패턴(pat)을 검색하여 텍스트의 위치(인덱스) 반환