트라이(Trie)

 

 

개념은 매우 간단하다. 여기보면 이해하기 쉬운편(PS관점에서 trie에 관한 다른 인사이트도 얻을 수 있다)

단어가 끝나는 지점에 마킹해야함에 유의

 

글자단위 Trie

아래는 내가 구현해본 Trie코드이며, 이 문제의 답안이기도 하다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
 
struct trie {
    struct node { map<char, node> child; bool end = false; };
    node root;
    node* insert(node* n, char c) {
        auto& m = n->child;
        if (m.count(c) == 0) m[c] = node();
        return &m[c];
    }
    void insert(string s) {
        node* n = &root;
        int m = s.length();
        for(int j=0;j<m;j++) n = insert(n, s[j]);
        n->end = true;
    }
 
    node* find(node* n, char c) {
        auto& m = n->child;
        if (m.count(c) == 0) return NULL;
        return &m[c];
    }
 
    bool find(string s) {
        node* n = &root;
        int m = s.length();
        for (int j = 0; j < m; j++) {
            n = find(n, s[j]);
            if (n == NULL) return false;
        }
        return n->end;
    }
};
 
int32_t main()
{
    int N, M; cin >> N >> M;
    trie t;
    REP(i, N) {
        string s; cin >> s;
        t.insert(s);
    }
    int ans = 0;
    REP(i, M) {
        string s; cin >> s;
        ans += t.find(s) ? 1 : 0;
    }
    cout << ans << '\n';
    return 0;
}

 

단어단위 Trie

이건 응용인데 글자단위와 비슷한 개념으로 풀 수 있다. 이 문제 참조.