[Algorithm] C - 브루트 포스(Brute Force)를 이용한 문자열 검색

요약

시간 복잡도 : 최상 O(n) 최악 O(mn)

• 브루트 포스 알고리즘이란 완전탐색 알고리즘으로 문제에 나와있는 모든 경우의 수를 시험하는 방법
• 찾고 싶은 문자열이 있을 때 각각의 문자 하나하나 대조하며 찾아내는 방법
• 검색할 문자열의 커서와 찾을 문자열의 커서를 두고 한 문자씩 비교
• 구조가 간단하여 구현 및 이해가 쉽지만 비효율적 알고리즘

브루트-포스법(Brute force) 알고리즘

브루트 포스 알고리즘이란 완전탐색 알고리즘으로 문제에 나와있는 모든 경우의 수를 시험하는 방법이다.
문자열을 검색하는 가장 기초적인 알고리즘으로 꼽히며 찾고 싶은 문자열이 있을 때 하나하나 대조하며 찾아낸다.

브루트 포스 알고리즘은 구조가 간단하여 구현 및 이해가 쉽지만 비효율적 알고리즘이다.

아래 예제는 문자열 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트 포스 알고리즘을 이용하여 검색하는 예제이다.

먼저 텍스트의 첫 문자 'A'부터 시작하는 3개의 문자와 "ABC"가 일치하는지 검사한다.
'A'와 'B'는 일치하지만, 'C'가 일치하지 않는다.

패턴을 1칸 뒤로 옮기고, STRING의 2번째 문자부터 3개의 문자가 일치하는지 검사한다.
'A'와 'B'가 다르다.

패턴을 다시 1칸 뒤로 옮기고, STRING의 3번째 문자부터 3개의 문자가 일치하는지 검사한다.
모두 일치하므로, 문자열 검색에 성공한다.

문자열 검색을 하기 위해 검색할 문자열의 커서와 찾을 문자열의 커서를 두고 한 문자씩 비교한다.
한 문자씩 비교하여 두 커서의 값이 동일할 경우, 문자열 검색에 성공했다고 판단한다.

서로 다른 문자일 경우 검색할 문자열의 커서를 다음 문자로, 찾을 문자열의 커서는 0으로 초기화 해서 재 비교한다.

 

예제 코드

#include <stdio.h>

int BruteForce(const char *text, const char *partition);

int main() 
{
    int index;
    
    // 검색할 문자열 "ABABCDEFGHA"
    char s1[256];
    
    // 찾을 문자열 "ABC"
    char s2[256];
    
    printf("검색할 문자열 : ");
    scanf("%s", s1);
    
    printf("찾을 문자열 : ");
    scanf("%s", s2);
    
    index = BruteForce(s1, s2);
    
    if(index == -1) {
        printf("문자열 검색 실패!\n");
    }
    else {
        printf("%d 번째 문자부터 동일합니다.\n", index + 1);
    }

    return 0;
}
int BruteForce(const char *text, const char *partition)
{
    // 검색할 문자열 커서
    int textCursor = 0;
    
    // 찾을 문자열 커서
    int partitionCursor = 0;
    
    while(text[textCursor] != '\0' && partition[partitionCursor] != '\0') {
        // 바라보고 있는 문자가 겹치는지 검사
        if(text[textCursor] == partition[partitionCursor]) {
            // 겹칠 경우 다음 문자 검색
            textCursor++;
            partitionCursor++;
        }
        else {
            // 검색할 문자열에서 다음 문자부터 검사할 커서 이동
            textCursor = textCursor - partitionCursor + 1;
            
            // 찾을 문자열 커서 0으로 업데이트
            partitionCursor = 0;
        }
    }
    
    // 찾을 문자열 커서가 끝에 도달했을 경우 문자열 검색 성공
    if(partition[partitionCursor] == '\0') {
            return textCursor - partitionCursor;
    }
    
    // 문자열 검색 실패
    return -1;
}

 

실행 결과

검색할 문자열 : ABABCDEFGHA
찾을 문자열 : ABC
3 번째 문자부터 동일합니다.

 

https://github.com/JeHeeYu/Algorithm/tree/main/String/Brute%20Force%20Method

GitHub - JeHeeYu/Algorithm: 알고리즘 개념 및 문제 풀이

 

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문: C 언어 편