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;
}
invalid-file
GlanceQry.tar
