문자열 검색: 브루트-포스법(Brute force method)

검색할 문자열을 패턴(pattern), 문자열 원본을 텍스트(text)라고 함

 

• 프루트-포스법

텍스트의 첫 문자부터 1칸씩 옮기며 순서대로 패턴과 비교

이전에 검사를 진행한 위치를 기억하지 못하므로 효율이 좋지 않음

 

#include <stdio.h>

int bf_match(const char txt[], const char pat[]){
  int pt = 0; //txt 커서
  int pp = 0; //pat 커서
  while(txt[pt] != '\0' && pat[pp] !='\0'){
    if(txt[pt] == pat[pp]){
      pt++;
      pp++;
    }
    else{
      pt = pt - pp +1;
      pp = 0;
    }
  }
  if(pat[pp] == '\0') return pt-pp;
  return -1;
}

int main(void){
  int idx;
  char s1[256];
  char s2[256];

  puts("브루트-포스법");
  printf("텍스트 : ");
  scanf("%s",s1);

  printf("패턴 : ");
  scanf("%s",s2);

  idx = bf_match(s1, s2);

  if(idx==-1) puts("텍스트에 패턴이 없습니다.");
  else printf("%d번째 문자부터 match합니다.\n", idx + 1);

  return 0;
}

 

시간복잡도: 텍스트 문자 개수 n, 패턴 문자 개수 m일 때 O(mn), 보통 O(n)