글 읽기 - 왜 해시에서 출돌이 일어나지 않는지 모르겠습니다.

na982 7년 전 0

인터넷에서 코드를 참조하여, 다시 구현하였습니다.

PRIME_1과 PRIME_2 을 이용해서 1개의 hash key를 두개의 hashes를 만들고,

PRIME_1을 이용해서 만든 값을 기준으로 정렬하여,

PRIME_1과 PRIME_2를 이용해서 만든 두개의 값이 모두 같은 경우에는 두 문자는 일치한다 라는 식으로 코드를 구현하였는데,

정답이 나왔습니다;

그런데 이게 왜 정답인지 잘 모르겠습니다.

xxx 가 PRIME_1으로 만든 값이 123이고, PRIME_2만든 값이 245 라고 가정한다면,

abc 가 PRIME_1으로 만든 값이 123, PRIME_2만든 값이 245, 가 절대 될수 없는것인지, 이부분이 잘 이해가 가지 않습니다;

어떤 부분을 공부해야 해당 내용을 이해 할수 있을까요??;;

아니면 테스트 인풋이 적어서 우연히 답이 맞은건가요?;

#include <cstdio>
using namespace std;

#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define SIZE	(1501)

#define PRIME_1	(999970207)
#define PRIME_2	(999970201)
#define PRIME_3	(999970189)

int isprime(int x)
{
	int i;
	for (i = 2; i*i <= x; i++)if (x%i == 0)return 0;
	return 1;
}

struct HASH {
	long long first;
	long long second;
};

int an, bn;
char a[SIZE], b[SIZE];
HASH alpha[26];
HASH total_a[(SIZE * SIZE) / 2];

void sort(int left, int right)
{
	if (left >= right)	return;

	int l = left - 1;
	int r = right + 1;
	long long mid_val = total_a[(l + r) / 2].first;
	HASH temp;
	while (1) {
		while (mid_val > total_a[++l].first);
		while (mid_val < total_a[--r].first);
		if (l >= r)	break;
		temp = total_a[l], total_a[l] = total_a[r], total_a[r] = temp;
	}
	sort(left, l - 1);
	sort(r + 1, right);
}

int search(int left, int right, HASH key) {
	if (left > right)	return -1;
	int mid_index = (left + right) / 2;
	HASH mid = total_a[mid_index];
	
	if (key.first < mid.first) {
		search(left, mid_index - 1, key);
	}
	else if (key.first > mid.first) {
		search(mid_index + 1, right, key);
	}
	else {
		return mid_index;
	}
}

int main()
{
	scanf("%s %s", a, b);
	for (an = 0; a[an]; ++an);
	for (bn = 0; b[bn]; ++bn);
	
	alpha[0].first = 1, alpha[0].second = 1;
	for (int i = 1; i < 26; ++i) {
		alpha[i].first = (alpha[i - 1].first * PRIME_3) % PRIME_1;
		alpha[i].second = (alpha[i - 1].second * PRIME_3) % PRIME_2;
	}

	int total_a_cnt = 0;
	for (int i = 0; i < an; ++i) {
		HASH temp = {0LL, 0LL };
		for (int j = i; j < an; ++j) {
			temp.first = (temp.first + alpha[a[j] - 'a'].first) % PRIME_1;
			temp.second = (temp.second + alpha[a[j] - 'a'].second) % PRIME_2;
			total_a[total_a_cnt++] = temp;
		}
	}
	sort(0, total_a_cnt - 1);
	int ret = 0;
	for (int i = 0; i < bn; ++i) {
		HASH key = { 0LL, 0LL };
		for (int j = i; j < bn; ++j) {
			key.first = (key.first + alpha[b[j] - 'a'].first) % PRIME_1;
			key.second = (key.second + alpha[b[j] - 'a'].second) % PRIME_2;
			int index = search(0, total_a_cnt - 1, key);
			if (index != -1) {
				for (int k = index; k >= 0; --k) {
					if (key.first == total_a[k].first) {
						if (key.second == total_a[k].second) {
							ret = MAX(ret, j - i + 1);
						}
					}
					else {
						break;
					}
				}
				for (int k = index + 1; k < total_a_cnt; ++k) {
					if (key.first == total_a[k].first) {
						if (key.second == total_a[k].second) {
							ret = MAX(ret, j - i + 1);
						}
					}
					else {
						break;
					}
				}
			}
		}
	}
	printf("%d\n", ret);
	return 0;
}

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

문제

문제

출처

ICPC

왜 해시에서 출돌이 일어나지 않는지 모르겠습니다.

na982 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말