문자열 검색: KMP법

• KMP법

텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구함

패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높임

 

• '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 표로 만들어 저장 (건너뛰기 표, skip table)

-> 패턴 내에서 중복되는 문자의 나열을 먼저 찾아야 함. 패턴과 패턴을 한 칸씩 비교 !

연속해서 겹치는 횟수를 기록

 

예를 들어 패턴이 "ABCABD"일 때,

    4번째에서 처음 겹치고(1) 5번째에서 연속으로 겹친다(2)

    따라서 건너뛰기 표는 "- 0 0 1 2 0"가 된다.

 

skip[idx]: idx번째 문자가 일치하지 않을 때 다시 되돌아가야 할 위치 !

 

• KMP법으로 문자열 검색

#include <stdio.h>

int kmp_match(const char txt[], const char pat[]){
  int pt = 1; //txt 커서
  int pp = 0; //pat 커서
  int skip[1024];
  
  skip[pt] = 0; //패턴끼리 비교하므로 비교되는 패턴을 텍스트로 가정
  while(pat[pt] != '\0'){ // 건너뛰기 표 만들기
    if(pat[pt] == pat[pp]) 
      skip[++pt] = ++pp;
      /*일치하므로 pt 다음에서 일치하지 않으면 pp 다음부터 비교하면 됨*/
    else if(pp == 0)
      skip[++pt] = pp; 
      /*처음부터 일치하지 않으면 pt 다음부터는 0번부터 다시 비교
      pt+1부터 다시 검색*/
    else pp = skip[pp];
     /*중간에 일치하지 않으면 skip[pp]로 돌아가서 다시 비교*/
  }

  pt = pp =0; //검색
  while(txt[pt] != '\0' && pat[pp] != '\0'){
    if(txt[pt] == pat[pp]){
      pt++; 
      pp++;
    }
    else if(pp == 0) pt++;
    else pp = skip[pp]; //문자열이 다르면 skip[pp] 문자열부터 비교 시작
  }
  if(pat[pp] == '\0') return pt - pp;

  return -1;
}

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

  puts("KMP법");
  printf("텍스트 : ");
  scanf("%s",s1);

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

  idx = kmp_match(s1, s2);

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

  return 0;
}

 

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