본문 바로가기

자료구조 & 알고리즘/문자열 매칭 알고리즘

[박혜웅] Brute Force(BF)

  • Brute Force 의 특징

    • 가장 간단한 문자열 탐색 알고리즘
    • 텍스트에서 모든 가능한 위치에 패턴이 일치하는지 검사
    • 전처리과정이 필요없음
    • 문자가 불일치할때 마다, 텍스트에 대한 윈도우(window)는 왼쪽에서 오른쪽으로 1식 이동한다.
    • 성능

      • text의 길이: n , pattern의 길이 m
      • 시간복잡도:

        • 평균 시간복잡도: O(n)
        • 최악의 시간복잡도: O(nm)

 

 

  • Brute Force 설명

 

 

  • Brute Force 의 실행

 

 

 

  • Brute Force 소스
  1. void BF(char *x, int m, char *y, int n) {
       int i, j;

       /* Searching */
       for (j = 0; j <= n - m; ++j) {
          for (i = 0; i < m && x[i] == y[i + j]; ++i);
          if (i >= m)
             OUTPUT(j);
       }
    }

 

  • Brute Force 소스(개선버전)
  1. #define EOS '\0'  
    void BF(char *x, int m, char *y, int n) {
      char *yb;
      /* Searching */
      for (yb = y; *y != EOS; ++y)
        if (memcmp(x, y, m) == 0)
          OUTPUT(y - yb);
    }