글 읽기 - 해싱기반으로 푸는데 런타임에러 질문드립니다.

godgod732 4년 전 0

도저히 어디서 런타임에러가 뜨는지 모르겠네요 ㅠㅠ

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX_LEN 20
#define MAX_TABLE 2000000
#define PRIME 31
using namespace std;
char hash_table[MAX_TABLE][MAX_LEN+1];
char ans_table[500005][MAX_LEN+1];
int ans_idx[500005];
int ansSize;
bool cmp(int  n1,int n2) {
	int result = strcmp(ans_table[n1], ans_table[n2]);
	if (result == 1) return false;
	else return true;
}
//hash
unsigned int getHash(char * key) {
	int p = 1;
	unsigned int hashV = 0;
	int idx = 0;
	while (key[idx] != '\0') {
		hashV = (hashV + (p*key[idx])) % MAX_TABLE;
		p *= PRIME;
		idx++;
	}
	return hashV;
}
//find
bool find(char * key) {
	unsigned int hashV = getHash(key);
	while (hash_table[hashV][0] != 0) {
		if (strcmp(hash_table[hashV], key) == 0) {
			return true;
		}
		hashV = (hashV + 1) % MAX_TABLE;
	}
	return false;
}
//add
bool add(char * key) {
	unsigned int hashV = getHash(key);
	while (hash_table[hashV][0] != 0) {
		if (strcmp(hash_table[hashV], key) == 0) {
			return false;
		}
		hashV = (hashV + 1) % MAX_TABLE;
	}
	strcpy(hash_table[hashV], key);
	return true;
}
int main() {
	int n, m;
	char name[MAX_LEN + 1];
	//초기화
	for (int i = 0; i < MAX_TABLE; i++) {
		hash_table[i][0] = 0;
	}
	scanf("%d%d", &n, &m);
	//듣지도 못한 사람
	for (int i = 0; i < n; i++) {
		scanf("%s", name);
		add(name);
	}
	//보지도 못한 사람
	for (int i = 0; i < m; i++) {
		scanf("%s", ans_table[ansSize]);
		//듣보잡 추가
		if (find(ans_table[ansSize])) {
			ans_idx[ansSize] = ansSize;
			ansSize++;
		}
	}
	printf("%d\n", ansSize);
	sort(ans_idx, ans_idx + ansSize, cmp);
	for (int i = 0; i < ansSize; i++) {
		printf("%s\n", ans_table[ans_idx[i]]);
	}

	return 0;
}

nahwasa 4년 전 0

while (key[idx] != '\0') {
hashV = (hashV + (p*key[idx])) % MAX_TABLE;
p *= PRIME;
idx++;
}
에서 PRIME이 31이고,
문자열의 최대길이는 20이하입니다.
p는 int이고, 31^19는 ‭21,670,662,219,970,396,194,714,277,471‬ 입니다.