[알고리즘] 부르트 포스(Brute-Force) 알고리즘 - 코딩밥상

부르트 포스(Brute-Force)란?

부르트 포스란 일차원적으로 앞에서부터 끝까지 차근차근 탐색하는 알고리즘입니다. 즉 모든 경우의 수를 모두 따지는 것입니다.

이 알고리즘은 마치 요령 부리지 않고 우직하게 일하는 일꾼처럼 동작합니다. 따라서 고지식한 탐색이라고도 합니다. 

이를 문자열 탐색에 사용한다면, 본문의 길이를 M, 패턴 길이를 N이라고 했을 때 본문 속에 있는 패턴을 찾기 위해 최악의 경우 N*M번의 비교를 수행합니다.

---

구현

int BruteForce(char* Text, int TextSize, int Start, char* Pattern, int PatternSize){
    for(int i=Start; i<=TextSize-PatternSize; i++){	//본문의 한글자씩 비교해가며 패턴 찾기
        for(int j=0; j<PatternSize; j++){
            if(Text[i+j] != Pattern[j]) break;
        }
        
        if(j >= PatternSize) return i;
    }
    
    return -1;
}