[gcc] 스트링 매칭 | kmp 알고리즘으로 grep 따라 하기~ Knuth, Morris, Pratt

http://suite.tistory.com/ fs 2007 04

주석을 달았는데도 뭔말인지 모르겠다 ㅎㅎ

원래는 BM(Boyer Moore)의 문자열 매칭 알고리즘을 할려고했는데~

불일치(bad character)방책은 되는데 일치 접미부(good suffix) 방책은 이해는가지만 구현이 안된다 ~.~

먼저 KMP의 구현을 봐야 일치 접미부도 구현할수있을것 같다~

BM는 나중에 시간나면 공부를 다시 ~.~

KMP

- 중복 패턴에 대한 사전정보를 미리 만든다 ( kmp 테이블생성 | 실패함수)

  ex)   index : 0 1  2  3  4  5   6
       pattern : A B C  D A  B  D 
         prefix : 0  0 0  0  1   2  0
   찾을 문자열 앞 AB와 뒤부분 AB가 일치함으로 뒤의 AB index 4,5부분의 kmp 테이블(사전중복테이블)에 각 1,2값을

  얻어 추후 중복 으로 검색 할 필요없게? 한다  

- 중복 패넡 사전정보를 가지고  불일치가 일어나지 않는 앞부분은  다시 비교하지 않는다(kmp 테이블이용 failure function )

- kmp 아무래도 중복이 자주 일어나는 패턴에는 좋을 효과를 얻을수 있는 알고리즘 같지만 일반 텍스트 에서는 BM 이 좀더

   효율적인 알고리즘이 될 것 같다. 왜냐하면 찾을 문자(패턴)를 뒷글자부터 매칭을 시도하기 때문이다~

  즉 한국말이나 영어들이 철자 앞부분보단 단어 마지막 철자들 변화가 많이 생길 가능성이  많으므로~

fs_grep.c

/* http://ppcast.cs.vt.edu/prod/ppCast/files/html/334/img12.html */

#include <stdio.h>
#define PSIZE   256

/* strlen(pattern) + 1 */
#define XSIZE   1024

int preKmp(char *pattern_str,int pattern_len, int kmpNext[])
{

 if(pattern_str==NULL) return -1;
 
 int i=1;
 int matches=0;

 while (i < pattern_len){

  // 같은 글자인지 확인후 매칭 카운트를 올린다.
  if(pattern_str[i] == pattern_str[matches]){
   matches++;
   kmpNext[i]=matches;
   i++;
   //다음 글자 확인해본다
   continue;
  }

  // 이전 글자(matches-1)와는 매칭 했지만 현재 글자(i)와 매칭 하지않을 경우
  if( matches > 0 ){
   matches=kmpNext[matches -1];
   // 이전글자와 확인해본다
   continue;
  }
  //매칭 하는 글자가 없거나 이전 글자와도 매칭 하지않을 경우
  i++;

 }
 return 0;
 
}

int main(int argc , char* argv[])
{

 FILE *fp;
 char pattern_str[PSIZE];
 char file_path[PSIZE];
 char line_buf[XSIZE];
 int i, matches, kmpNext[XSIZE];
 int line_cnt=0;
 int line_len=0;
 int pattern_len=0;

 if(argc != 3) {

  printf("\n[Usage] %s <pattern_str> <file_path>\n",argv[0]);
  return ;
 }
 strcpy(pattern_str,argv[1]);
 strcpy(file_path,argv[2]);

 for(i=0;i<XSIZE;i++){
  kmpNext[i]=0;
 }

  pattern_len=strlen(pattern_str);

 if( ! (fp=fopen(file_path,"r"))){
                printf("File Not Found (%s)\n",file_path);
                return -1;
        }
 
 // 일치하지 않을경우 위치를 옮길수? 있도록 kmp 테이블을 생성한다.
 preKmp(pattern_str,pattern_len, kmpNext);

 while(1)
 {

  if(fgets(line_buf,sizeof(line_buf),fp)==NULL) break;
  line_cnt++;
  line_len=strlen(line_buf);

  // 한줄에 해당하는 라인을 탐색한다.
  i = 0;
  matches = 0;
  while ( i < line_len ) {

   if ( line_buf[i] == pattern_str[matches] ) {
    matches++;
    // matches 값과 찾는 패턴의 길이가  같으면 찾은것으로 판단.
    if ( matches == pattern_len){
     printf("[LINE:%d] %s",line_cnt,line_buf);
    }else i++;

    //다음 문자 검색
    continue;
   }

   // 이전문자와 매칭 한적이 있을경우
   if ( matches > 0 ){
    matches = kmpNext[matches - 1];
    continue;
   }

   // 매칭이 이전과 현재 전혀 없는 경우
   i++;
  }

 }//end of while(1)

 return 0;

}