글 읽기 - 해싱 문제 어디서 틀린걸까요?

chisukj 5년 전 0

해싱 문제 어디서 틀린걸까요?

#include <stdio.h>
#include <string.h>
#define MAX_TABLE 50423
using namespace std;

int T;
int n;
char tmp[11];
char tmp2[11];

typedef struct
{
	char key[11];
}Hash;
Hash tb[MAX_TABLE];

unsigned long hash(const char *str)
{
	unsigned long hash = 5381;
	int c;
	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}
	return hash % MAX_TABLE;
}

int find(const char *key)
{
	unsigned long h = hash(key);
	int cnt = MAX_TABLE;
	while (tb[h].key[0] != 0 && cnt--)
	{
		if (strcmp(tb[h].key, key) == 0)
		{
			return 1;
		}
		h = (h + 1) % MAX_TABLE;
	}
	return 0;
}

int add(const char *key)
{
	unsigned long h = hash(key);
	while (tb[h].key[0] != 0)
	{
		if (strcmp(tb[h].key, key) == 0)
		{
			return 0;
		}
		h = (h + 1) % MAX_TABLE;
	}
	strcpy(tb[h].key, key);
	return 1;
}

int main()
{
	scanf("%d", &T);
	for (int test = 1; test <= T; ++test)
	{
		memset(tb, 0, sizeof(tb));
		int flag = 0;
		scanf("%d", &n);
		for (int i = 0; i < n; ++i)
		{
			scanf("%s", &tmp);
			if (i > 0)
			{
				int a = 0;
				while (tmp[a] != NULL)
				{
					for (int j = 0; j <= a; ++j)
						tmp2[j] = tmp[j];
					if (find(tmp2) == 1)
						flag = 1;
					++a;
					for (int j = 0; j < a; ++j)
						tmp2[j] = 0;
				}
			}

			add(tmp);
		}
		if (flag == 1)
			printf("NO\n");
		else
			printf("YES\n");
	}
}

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

문제

문제

출처

ICPC

해싱 문제 어디서 틀린걸까요?

chisukj 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말