글 읽기 - 라빈 카프로 풀수 있는 문제인가요?

cocobo123 5년 전 0

안녕하세요?

이번 찾기 문제를 라빈 카프로 풀려다가 계속 시간초과가 발생해서 궁리해봤더니

찾으려는 pattern이 길이가 너무 길면 해시값이 맞아도 해시값이 맞는지 strcmp 할 때 시간으로 시간초과가 나지 않을까라는 생각이 들었습니다.

그렇다고 strcmp를 하지 않고 해시값만으로 pattern 일치여부를 했더니 틀렸다고 나옵니다.

제가 코드를 잘못 짰을 가능성두 있을거 같네요.

첨언 부탁드립니다.

#include<stdio.h>
#define Max 1000001
#define mod 1000000007
char string[Max], pattern[Max];
int idx[Max];
int N,len;
int strcmp(char * ahead, char * behind, int len) {
	for (int i = 0; i<len; i++)
		if (ahead[i] != behind[i])
			return ahead[i] - behind[i];
	return 0;
}
void RabinKarp(char * string, char * pattern) {
	//1. 패턴의 해시값 구하기
	long long pkey = 0;
	long long pwr = 1;
	for (len = 0; pattern[len]; len++) {
		pkey = (pkey + pattern[len]) % mod;
		pkey = (pkey * 2) % mod;

		pwr = (pwr * 2) % mod;
	}

	long long skey = 0;
	for (int i = 0; pattern[i]; i++)
		skey = (skey + string[i])*2 % mod;
	
	int cnt = 0;
	for (int i = 0; string[i+len-1]; i++) {
		if (pkey == skey) {
			//if (strcmp(pattern, &string[i],len) == 0)
				idx[cnt++] = i + 1;
		}
		skey = (skey - (string[i] * pwr)) % mod+mod;
		skey = (skey + string[i + len])*2 % mod;
	}
	printf("%d\n", cnt);
	if (cnt) {
		for (int i = 0; i < cnt; i++)
			printf("%d ", idx[i]);
		printf("\n");
	}
	return 0;
}

int main() {
	gets(string);
	gets(pattern);

	RabinKarp(string, pattern);

	return 0;
}

djm03178 5년 전 0

100만자리에서 10억7의 모듈로는 충돌 확률이 매우 높지 않을까 생각합니다.

cocobo123 5년 전 0

감사합니다.

그러면 strcmp가 반드시 필요한 사항이잖아요?

그런데 strcmp를 했을 경우에는 시간초과가 발생합니다.

본문 : aaaaaaaaa ...aaaaaaa

패턴 : aaaaaaaaa...aaaaa

처럼 일 때 아무래도 계속 strcmp를 해서 시간이 초과된다고 짐작합니다만

혹시 개선방법이 있을까요?

djm03178 5년 전 1

mod 10억7 말고 훨씬 큰 수로 하면 됩니다. long long 범위 전체를 사용한다면. 해시 함수만 잘 만들면 사실상 충돌이 없다고 볼 수 있습니다.

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

문제

문제

출처

ICPC

라빈 카프로 풀수 있는 문제인가요?

cocobo123 5년 전 0

djm03178 5년 전 0

cocobo123 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말