[백준 1764] 듣보잡(해시 구현)

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

1764번: 듣보잡

요구사항

1. 해시를 구현하여 해시테이블안에 value가 존재 시 vector에 추가 해주어 정답 출력

 

#include <stdio.h>
#include <map>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

const int PN = 23;//소수
const int HASH_SIZE = 50001; //해시 사이즈

int table[HASH_SIZE][100]; //해시 테이블 리스트를 위해서 2차원 배열으로
int hash_size = 0;
char hash_raw[HASH_SIZE][100]; //인덱스에 따라 자료를 저장

char input[30000][100]; // 입력

map<char*, int> test;
vector<string> v;
unsigned int get_key(char str[])
{
	unsigned int key = 0, p = 1;
	for (int i = 0; str[i] != 0; i++)
	{
		key += (str[i] * p);
		p *= PN;
	}


	return (key%HASH_SIZE);
}


int my_strcmp(char a[], char b[])
{
	int i = 0;
	int j = 0;
	while (a[i])
	{
		if (a[i++] != b[j++]) {
			i--; j--;
			break;
		}
	}
	return (a[i] - b[i]);
}


void add(char str[])
{
	//hash raw에다가 문자열 넣기
	//hash size라는 칸에다 현재 문자열을 넣는다.
	int len = 0;
	for (len = 0; str[len] != 0; len++)
	{
		hash_raw[hash_size][len] = str[len];
	}
	hash_raw[hash_size][len] = 0;

	unsigned int key = get_key(str);
	int& size = table[key][0];
	//table에는 key 해당하는 hash_size index번호를 넣는다
	table[key][++size] = hash_size;

	hash_size++;

}


int contain(char str[])
{
	unsigned int key = get_key(str);
	int size = table[key][0];
	for (int i = 1; i <= size; i++)
	{
		int pos = table[key][i];
		if (my_strcmp(hash_raw[pos], str) == 0) {
			return pos;
		}
	}
	return -1;
}

bool remove(char str[])
{
	unsigned int key = get_key(str);
	int& size = table[key][0];
	for (int i = 1; i <= size; i++)
	{
		int pos = table[key][i];
		if (my_strcmp(hash_raw[pos], str) == 0)
		{
			for (int j = i + 1; j <= size; j++)
			{
				table[key][j - 1] = table[key][j];
			}
		}
		size--;
		return true;
	}
	return false;
}


int main()
{
	ios_base::sync_with_stdio(false);
	int n, m;
	scanf("%d%d", &n , &m);
	for (int i = 0; i < n; i++)
	{
		char ch[21];
		scanf("%s", ch);
		add(ch);
	}
	for (int i = 0; i < m; i++)
	{
		char ch[21];
		scanf("%s", ch);
		if (contain(ch) != -1)
			v.push_back(ch);
	}
	cout << v.size() << endl;
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
	{
		cout << v.at(i) << "\n";
	}
}