뇌자알 KMP 알고리즘 소스보다가 의문점

성대아싸(115.145) 2009.10.07 10:04:57

조회 143 추천 0 댓글 2

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_BUF 512

void preproc(char* pat, int pat_size, int* border)

{

int i = 0;

int j = -1;

int k;

border[0] = -1;// 첫번째 경계 너비는 -1 이다.

while(i < pat_size)

{

while(j > -1 && pat[i] != pat[j])

j = border[j];

i++;

j++;

border[i] = j;

}

for(k=0; k<pat_size+1; k++)

printf("%d ", border[k]);

printf("\\n");

}

int KMP(char* text, int text_size, int start, char* pat, int pat_size)

{

int i = start;

int j = 0;

int position = -1;

int* border = (int*)calloc(pat_size+1, sizeof(int));

preproc(pat, pat_size, border);

while(i < text_size)

{

while(j >= 0 && text[i] != pat[j])

j = border[j];

i++;

j++;

if(j == pat_size)

{

position = i - j;

break;

}

free(border);

return position;

}

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

{

char* filepath;

FILE* fp;

char text[MAX_BUF];

char* pat;

int pat_size = 0;

int line = 0;

int position;

if(argc < 3)

{

printf("%s <filepath> <pattern>\\n", argv[0]);

return 1;

}

filepath = argv[1];

pat = argv[2];

pat_size = strlen(pat);

if((fp = fopen(filepath, "r")) == NULL)

{

printf("cannot open file: %s\\n", filepath);

return 1;

}

while(fgets(text, MAX_BUF, fp) != NULL)

{

position = KMP(text, strlen(text), 0, pat, pat_size);

line++;

if(position >= 0)

{

printf("line:%d, col:%d : %s", line, position+1, text);

}

fclose(fp);

return 0;

}

preprocess로 border 만드는데

패턴에 대해서 한번만 만들면 되는거 아님니카?

KMP 내에 있어 호출시마다 계속 만드는데영

fgets로 라인단위로 호출해서 어쩔슈 없는겁니카?

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	연예인 안됐으면 어쩔 뻔, 누가 봐도 천상 연예인은?	운영자	24/06/17	-	-
164565	[뻘글] 횽들은 회사다닐때 정장입고 출근해? [12]	CCC(203.237)	09.12.29	196	0
164564	한국 게임시장은 불법으로 시작해서 [4]	Vita500	09.12.29	129	0
164562	형들은 지금 사고 싶은거 모 있음?? [17]	MonQ(220.121)	09.12.29	143	0
164560	혹시 Crypto++ 로 RSA 암/복호화 해본 형 있음? [3]	프뤠	09.12.29	629	0
164558	공장에 전산팀 취직하는건 어때요? [5]	임베디드(112.150)	09.12.29	171	0
164557	프갤에 삼국지 덕후 있냐능? [9]	아주아슬	09.12.29	113	0
164555	대학..... 결과가 나왔다..... [2]	∫ 2t dt=t²+c	09.12.29	224	0
164554	프로그래밍하곤 별관계없는데//유동애들 ip 숨겨진거 보는방법혹시알아? [4]	리코인	09.12.29	167	0
164553	방학동안 윈도우 프로그래밍을 해볼까 하는데 [11]	URA!	09.12.29	193	0
164550	나 잘되길 빌어달라고 하면 빌어줄꺼냐 씹쌔들아?? [6]	개쉛기	09.12.29	155	0
164549	현재 횽들이 주로 쓰고 있는 프로그래밍 언어는? [3]	ㅁㅁ(180.67)	09.12.29	127	0
164548	횽들 컴퓨터구조 말인데.. [7]	링가링가링(119.69)	09.12.29	229	0
164546	숙신횽은 봄미다 [3]	nRST	09.12.29	78	0
164545	폰은 아이폰으로사고 개발은 안드로이드로... [1]	임베디드(112.150)	09.12.29	187	0
164542	성적 나왔다 [6]	Rei@디씨	09.12.29	191	0
164539	숙신은 봅니다. [28]	rntjr	09.12.29	265	0
164538	님들 나눔 폰트는 쓰면서 이러는거임? [9]	nRST	09.12.29	227	0
164537	2차원배열 초기화 어케하는겨~ [18]	신발라마	09.12.29	338	0
164535	뇌를 자극하는 프로그래밍 원리라는 책이 있던데. [6]	어떡해	09.12.29	320	0
164534	횽들 지금 졸라 급한 질문이 하나 있어.. [8]	물속의다이아	09.12.29	159	0
164533	오늘... [5]	ㅇㅇㅃ	09.12.29	139	0
164531	하루가 또 훌쩍 지나갔네	Vita500	09.12.29	94	0
164530	예전에 만들어둔 '다음 KIN보드' 이미지 수집기 소스. [3]	rntjr	09.12.29	201	0
164528	좋은 조공 및 짤방을 올릴수 있다는 것은... [1]	물속의다이아	09.12.29	210	0
164527	페이퍼타오리 요기잉네 [1]	ㅇㅇㅃ	09.12.29	146	0
164526	후로그래머는 투자 대비 효율이 너무 안좋은거 같음.. [2]	dd(115.92)	09.12.29	137	0
164525	형님드라 도와주세여 굽신	왜그랫니ㅠ	09.12.29	82	0
164524	더블포인터좀물어봅니다. [7]	ddd(115.143)	09.12.29	150	0
164522	연봉 실수령 금액 어떻게 계산함? [6]	ㅇㅇㅃ	09.12.29	282	0
164521	대학진학하는데질문드릡니다 [9]	굽굽굽네를원해(220.86)	09.12.29	124	0
164520	드래곤볼 온라인 재밌을까 [1]	출입증	09.12.29	86	0
164517	vb 관련 질문 하나만 더... [1]	강화인간	09.12.29	67	0
164516	아 오랜만에 뻘글을 싸봅시다. [3]	∫ 2t dt=t²+c	09.12.29	98	0
164515	스마트카드 작업 해본 횽아 있음? [8]	외계달팽	09.12.29	110	0
164514	트랜젝션 질문. spring ibatis [5]	usoo0	09.12.29	186	0
164513	문느님이 저에게 그러하셨습니다 [14]	개쉛기	09.12.29	181	0
164511	사직서 [1]	유리한	09.12.29	147	0
164510	[폭]아앜 최신 여자친구 사진 자랑하고 싶어서 현기증 날꺼 같단 말이에요 [6]	칭송받는자(210.118)	09.12.29	268	0
164509	[폭] 유리한을 위한 짤이라면 이정돈 되야 [9]	칭송받는자(210.118)	09.12.29	279	0
164506	아 진짜 중독성 쪈다 [4]	유리한	09.12.29	223	0
164505	C 간단한 질문좀 드릴게요 [4]	ㅋㅋㅋ(121.141)	09.12.29	96	0
164504	본격 "개쉛기" 횽 까는글 [2]	칭송받는자(210.118)	09.12.29	146	0
164503	왜 이화여대엔 꼴통이 많은걸까? [4]	그런데	09.12.29	237	0
164502	마봉춘에 임경아가 있다면 YTN엔 박수연이 있다. [4]	삼류(150.183)	09.12.29	365	0
164501	jsp 책 추천좀 해주세요 [4]	ㅁㄵ(218.154)	09.12.29	126	0
164500	뭔가 공황상태에 빠졌다... [7]	캐꼬꼬닭(112.216)	09.12.29	127	0
164499	숙신! [10]	NaCl	09.12.29	124	0
164498	뭐 재미있는거 없을까 [1]	유리한	09.12.29	99	0
164497	숙신횽은 봄미다. [1]	칭송받는자(210.118)	09.12.29	92	0
164496	당신의 IT 내공은 어느 수준임? [5]	ㅇㅇㅃ	09.12.29	229	0