[Algorithm][C++] BOJ 14425: 문자열 집합 (Hash)

url: https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

 

풀이 핵심

<Hash 풀이> (HashTable 구현 참고)

1. S 집합 문자열 hashTable에 저장

2. find 함수로 hashTable 검색

코드

#define MAXN		10000
#define MAX_TABLE	10007
#define MAXL		26
typedef unsigned long long ull;
#include <cstdio>

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

void mystrcpy(char* a, const char* b) { while (*a++ = *b++); }

int mystrcmp(const char* a, const char* b) {
	while (*a && *a == *b) ++a, ++b;
	return *a - *b;
}

struct String {
	char text[501];
	String* next;
} strings[MAXN], *hashTable[MAX_TABLE];

int N, M, ans;
char tmp[501];

int find(const char* text) {
	ull h = getHashCode(text);
	String* cur = hashTable[h];
	while (cur) {
		if (!mystrcmp(cur->text, text)) return 1;
		cur = cur->next;
	}
	return 0;
}

int main() {
	register int i;
	scanf("%d %d", &N, &M);

	for (i = 0; i < N; ++i) {
		scanf("%s", strings[i].text);
		ull h = getHashCode(strings[i].text);
		strings[i].next = hashTable[h];
		hashTable[h] = &strings[i];
	}

	for (i = 0; i < M; ++i) {
		scanf("%s", tmp);
		ans += find(tmp);
	}
	printf("%d", ans);
	return 0;
}