유년

유년

개발자

[SWEA] 2948 문자열 교집합 (C++, 라이브러리 X)

Hash 기본문제

풀이

첫번째 집합으로 Hash Table을 만든다.

두번째 집합의 문자열들이 Hash Table에 존재하는지 확인한다.

코드 GitHub

#include <iostream>
using namespace std;

#define MAXN 100000
#define MAX_LENGTH 51
#define HASH_SIZE (1 << 18)
#define DIV (HASH_SIZE - 1)

void StrCpy(char *empty, char *str) {
    while(*str) *empty++ = *str++;
    *empty = 0;
    return;
}

bool StrCmp(char *strA, char *strB) {
    while(*strA) {
        if(*strA++ != *strB++) return false;
    }
    return *strA == *strB;
}

int GetHash(char* str) {
    unsigned long long hash = 5381;
    while(*str) {
        hash = (hash << 5) + hash + *str - 'a';
        *str++;
    }
    return (int)hash & DIV; 
}

struct HashNode {
    char str[MAX_LENGTH];
    HashNode* next;
    HashNode* Alloc(char *_str, HashNode* _next) {
        StrCpy(str, _str);
        next = _next;
        return this;
    }
} nodes[MAXN];

HashNode* hashTable[HASH_SIZE];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    int N, M;
    char str[MAX_LENGTH];
    for(int tc = 1 ; tc <= T; tc++) {
        cin >> N >> M;
        int nodeCnt = 0;
        for(int i = 0; i < HASH_SIZE; i++) hashTable[i] = nullptr;
        for(int n = 0; n < N; n++) {
            cin >> str;
            int hash = GetHash(str);
            hashTable[hash] = nodes[nodeCnt++].Alloc(str, hashTable[hash]);
        }
        int ans = 0;
        for(int m = 0; m < M; m++) {
            cin >> str;
            int hash = GetHash(str);
            HashNode* node = hashTable[hash];
            while(node) {
                if(StrCmp(node->str, str)) {
                    ans++;
                    break;
                } else node = node->next;
            }
        }
        cout << '#' << tc << ' ' << ans << '\n';
    }
    return 0;
}

댓글남기기