[박혜웅] 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);
   }