글 읽기 - kmp도움 부탁드립니다

0613antonio 2년 전 0

중간에 무한루프를 돌아서 시간초과가 나는 것 같은데 이유를 모르겠습니다

#include<iostream>
using namespace std; 

int A[1000010]={};
int B[2000010]={}; 
int pie[1000010]={};
int as,bs;
int ans=0;

void pre_kmp(){//실패함수
	int i=1;
	int j;
	pie[0]=0;
	while(i<as){
		if(A[i]==A[0]){
		    pie[i]=1;
		    j=i+1;
		    while(A[j]==A[j-i] && j<as){
			    pie[j]=pie[j-1]+1;
			    j++;
		    }
		    i=j;
	    }
	    else{
		    pie[i]=0;
		    i++;
	    }
	}
}

int kmp(){
	int i=0;
	int j;
	pre_kmp();
	while(i<=bs-as){
		while(A[0]!=B[i] && i<=bs-as) i++;
		j=0;
		while(A[j]==B[j+i] && j+i<bs){
			j++;
		}
		if(j==as) ans++;
		i+=j-pie[j-1];
	}
	return -1;
}

int gcd(int a, int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf(" %c",&B[i]);
		B[i+n]=B[i];
	}
	B[2*n-1]=0;
	for(int i=0;i<n;i++){
		scanf(" %c",&A[i]);
	}
	as=n;
	bs=2*n-1;
	kmp();
	int g=gcd(ans,n);
	ans/=g; n/=g;
	printf("%d/%d",ans,n);
}

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

문제

문제

출처

ICPC

kmp도움 부탁드립니다

0613antonio 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말