글 읽기 - 잘 돌아가다가 런타임 에러로 바뀝니다.

khseob0715 6년 전 0

책에 있는 kmp 알고리즘을 토대로 만든 것이며

남은시간 7초? 21%? 이정도 쯤에서 런타임 에러로 바뀌게 됩니다.

제 생각에는

int *fi = (int*)malloc(sizeof(int)*(plen+1)); // 패턴만큼의 배열을 만든거

이 부분이 패턴의 100만개에 해당하는 배열을 못 만들어서 그런것 같은데

이러면 어떻게 해야될까요?

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

#define max_str  1000001
#define max_pat  1000001

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;
	while(j <= m){
		if( k == -1 || p[j] == p[k]){
			j++;
			k++;
			fi[j] = k;
		}else{
			k = fi[k];
		}

	}
}

void kmp(char a[],char p[], int fi[]){
	int cnt = 0;
	int i = 0;
	int j = 0;
	int n = strlen(a);
	int m = strlen(p);
	int res[100000];
	while(i < n){
		if(j == -1 || a[i] == p[j]){
			i++;
			j++;
		}else{	
			j = fi[j];		
		}
		if(j == m){
			res[cnt++]=i-j+1;
			j = fi[j];			
		}
	}
	printf("%d\n",cnt);
	for(int aa = 0; aa < cnt ; aa++){
		printf("%d\n",res[aa]);
	}

}


int main(){
	gets(str);
	gets(pat);
	int slen = strlen(str);
	int plen = strlen(pat); // 패턴의 길이 

	int *fi = (int*)malloc(sizeof(int)*(plen+1)); // 패턴만큼의 배열을 만든거
	preprocessing(pat,fi,plen+1);
	kmp(str,pat,fi);
}

doju 6년 전 0

패턴이 10만 번 넘게 등장할 수 있습니다.

khseob0715 6년 전 0

그럼 패턴이 100만개 있다고 가정한다면

int *res = (int*)malloc(sizeof(int)*max_str);

을 사용하고 제출하였는데 같은 구간에서 런타임 에러가 발생합니다.

100만개의 패턴을 저장하는 방법이 저게 아닌가요??

doju 6년 전 1

개인적으로는 malloc을 이용한 동적 메모리 할당을 (특히 PS에서는) 되도록 쓰지 않기를 권해 드립니다. https://algospot.com/forum/rea...

본인이 계속해서 malloc을 사용한 부분에 의구심을 가지는 것에서 보듯 정적 배열에 대해 얻는 이득도 없고 디버깅도 어려워집니다.

preprocessing 함수 내에서 j가 fi의 크기를 넘어가는 것으로 보입니다.

khseob0715 6년 전 0

설명 감사드립니다.

해결했습니다. =ㅁ=

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

문제

문제

출처

ICPC

잘 돌아가다가 런타임 에러로 바뀝니다.

khseob0715 6년 전 0

doju 6년 전 0

khseob0715 6년 전 0

doju 6년 전 1

khseob0715 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말