백준[14425] 문자열 집합

문제 설명

문제 링크

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

14425번: 문자열 집합

풀이

stl의 set을 이용하여 아주 간단하게 풀이할 수 있는 문제다.

하지만 trie를 공부하기 좋은 문제이므로 trie를 이용한 풀이도 해봤다.

코드

트라이

#include <cstdio>
#include <string>
#include <cstring>

using namespace std;

struct Trie {
    bool finish;
    Trie *child[26];

    Trie() : finish(false) {
        memset(child, 0, sizeof(child));
    }

    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (child[i]) delete child[i];
        }
    }

    void insert(const char *key) {
        if (*key == 0) {
            finish = 1;
            return;
        }
        int idx = *key - 'a';
        if (!child[idx]) child[idx] = new Trie();
        child[idx] -> insert(key + 1);
    }

    bool check(const char *key) {
        if (*key == 0) return finish;
        int idx = *key - 'a';
        if (!child[idx]) return false;
        bool ret = child[idx] -> check(key + 1);
        return ret;
    }
};

int main() {
    int N, M; scanf("%d %d", &N, &M);
    Trie *root = new Trie();
    while (N--) {
        char tmp[502]; scanf("%s", tmp);
        root -> insert(tmp);
    }
    int ans = 0;
    while (M--) {
        char tmp[502]; scanf("%s", tmp);
        if (root -> check(tmp)) ans++;
    }
    printf("%d", ans);
}

set

#include <iostream>
#include <string>
#include <set>

using namespace std;

set<string> s;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N, M; cin >> N >> M;
    while (N--) {
        string tmp; cin >> tmp;
        s.insert(tmp);
    }
    int ans = 0;
    while (M--) {
        string tmp; cin >> tmp;
        if (s.count(tmp)) ans++;
    }
    cout << ans;
}