c언어 14425번 문자열 집합 (백준)

#include <stdio.h>
#include <string.h>
//해쉬값 소인수 31, 1234567891
int main(void) {
	int cnt = 0; //정답
	int n, m;
	scanf("%d%d", &n, &m);

	long long int hash_in[n]; //집합 S에 있는 문자열들의 해쉬값
	int len_in[n]; //충돌 임시방편 집합 S에 있는 문자열들의 길이
	for(int i = 0; i<n; i++) { //0으로 초기화
		hash_in[i] = 0;
		len_in[i] = 0;
	}

	int tmp = n;
	while(tmp--) {
		int r = 1; //소인수 제곱을 위한 변수
		char s[502] = ""; //문자열을 입력받기 위한 변수
		scanf("%s", s);
		len_in[tmp] = strlen(s); //길이 저장
		for(int i = 0; i<len_in[tmp]; i++) { //해쉬값 만들기
			if(i>0) r *= 31;
			hash_in[tmp] += r * (s[i] - 0x61);
			hash_in[tmp] = hash_in[tmp] % 1234567891; //해쉬값 저장
		}
	}

	tmp = m;
	while(m--) { //비교할 문자열
		long long int hash = 0; //비교할 문자열의 해쉬값을 담을 변수
		int r = 1;
		char s[502] = "";
		scanf("%s", s);
		int len = strlen(s); //비교할 문자열의 길이
		for(int i = 0; i<len; i++) { //해쉬값 구하기
			if(i>0) r *= 31;
			hash += r * (s[i] - 0x61);
			hash = hash % 1234567891; 
		}

		for(int i = 0; i<n; i++) { //탐색 (집합 S에 있는지)
			if(hash == hash_in[i]) {//해쉬값이 같고
				if(len == len_in[i]) {//길이도 같다면
					cnt++; //같다라고 간주한다!
				}
			}
		}
	}
	printf("%d", cnt); 
	return 0;
}

풀이

1. 집합 S의 문자열들을 입력받으면서, 각각의 해쉬값 (소인수 31, 1234567891)과 길이를 저장한다.

2. 비교할 문자열의 해쉬값과 길이를 구하고, 앞서 저장한 집합 S에 있는 해쉬값과 길이와 동시에 같다면, 비교하는 문자열은 집합 S에 속한다고 간주한다.

3. 몇 개 속해있는지 출력한다.

 

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

14425번: 문자열 집합