글 읽기 - kmp 알고리즘을 작성하고 있습니다.

khseob0715 6년 전 0

죄송합니다. 해당 사이트에 존재하는 문제는 아니고요

알고리즘 공부하는 중에 kmp 알고리즘을 작성하고 있는데 잘 안 되서 질문 드려요

kmp 함수에서 j의 값이 계속 2로 유지가 되고 있는데 왜 그런건가요??

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define max_str  10000
#define max_pat  100

char str[max_str];
char pat[max_pat];

void preprocessing(char p[],int fi[], int m){

	int j = 0;
	int k = -1;
	fi[0] = -1;
//	printf("j: %d k: %d\n",j+1,k+1);
	while(j <= m){
		if( k == -1 || p[j] == p[k]){
			j++;
			k++;
			fi[j] = k;
		}else{
			k = fi[k];
		}
//		printf("j: %d k: %d\n",j+1,k+1);
	}
}

void kmp(char a[],char p[], int fi[]){
	int i = 0;
	int j = 0;
	int n = strlen(a);
	int m = strlen(p);

	while(i < n){
		printf("%c == %c\n",a[i],p[j]);
		if(j = -1 || a[i] == p[j]){
			i++;
			j++;
		}else{
			printf("false");
			j = fi[j];		
		}
        if(j == m+1){
			j = fi[j];			
		}
	}
}



int main(){
	scanf("%s %s",&str,&pat);
	int slen = strlen(str);
	int plen = strlen(pat);

	int *fi = (int*)malloc(sizeof(int)*(plen+1));
	int *st = (int*)malloc(sizeof(int)*slen);
	preprocessing(pat,fi,plen+1);
	kmp(str,pat,fi);
	for(int i = 0 ; i < plen+1; i++){
		printf("%d ",fi[i]);
	}printf("\n");

}

ntopia 6년 전 1

아마 37번째 줄 때문에 그런 것 같네요

j == -1 으로 써야할 것을

j = -1 로 쓰셔서

j에 -1이 대입되어버리네요

khseob0715 6년 전 1

와.. 이런 실수를 했을거라고는 상상고 못했습니다...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

kmp 알고리즘을 작성하고 있습니다.

khseob0715 6년 전 0

ntopia 6년 전 1

khseob0715 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말