ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Algorithm] Brute Force
    개발하면서/Algorithm,DS,PS 2010. 12. 3. 12:42
    반응형

    가장 간단한 알고리즘입니다.

    만약 찾고자 하는 패턴은 ABTBA, 원본 텍스트는 AAABTABTBAB일 경우 아래 그림과 같이 비교를 합니다.

     

    아래와 같은 방법으로 문자열을 찾습니다.

     

    패턴첫글자와 원본을 비교하면서 일치가되는것을 찾습니다.

    일치가 되었으면, 다음글자가 일치되는지 확인하고, 중간에 일치하지 않는다면 바로 다음칸으로 이동해서

    다시 패턴 첫 글자부터 일치여부를 판단합니다.

     

    구현이 간단하지만 비효율적인 문자열 검색 알고리즘 이네요.

     

    int main() {
      char str[12] = "AAABTABTBAB";
      char pattern[5] = "ABTBA";
      int i = 0;
      int j = 0;
    
      for (; i < 11; i++) {
        for (; j < 5; j++) {
          if (str[i+j] != pattern[j]) {
            break;
          }
        }
        if (j == 5) {
          printf("Find it: startOf(%d), %s \n", i, str+i);
          break;
        }
      }
      return 0;
    }
    반응형

    댓글

Designed by Tistory.