[백준 5446] 용량 부족

문제

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

 

알고리즘

트라이

 

풀이

제거해야 하는 문자열과 남겨야 하는 문자열이 주어지고, "문자열"+"*"을 통해 "문자열"로 시작하는 모든 문자열을 제거할 수 있다고 합니다. 접두사를 이용한다는 점에서 트라이를 착안해봅시다. 

 

각 노드마다 $yes$,$no$,$finish$ 를 만들어서 해당 노드를 제거해야하는지(yes), 제거해서는 안되는지(no), 제거해야 하는 문자가 끝나는지(finish)를 구분합니다. 만약 노드의 $yes$와 $no$가 둘 다 True 면 해당 노드를 제거해서는 안됩니다.

(노드를 제거한다는 것은 와일드 카드를 사용해서 이후 노드를 보지 않겠다는 의미입니다)

이때 유의해야할 것은, 제거해서는 안 되는 노드에 $finish$가 있다면, 와일드카드를 사용하지 않고 파일명을 다 적어서 제거하도록 합시다.

 

마지막으로 처음부터 와일드 카드를 사용할 수 있는 경우, 즉 제거해선 안 되는 문자열이 없다면 1을 출력하도록 해주면 됩니다. 공간 복잡도는 $O((N1+N2)*20*63*ptrsize)$입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

const int MAXV = 63;

int tc;
int A, B;

string s;

int conv(char c) {
    int ret = -1;
    if (c == 46) ret = 0;
    else if (48 <= c && c <= 57) ret = c - '0' + 1;
    else if (65 <= c && c <= 90) ret = c - 'A' + 11;
    else ret = c - 'a' + 37;
    return ret;
}


struct Trie {
    Trie* children[MAXV];
    bool no;
    bool yes;
    bool finish;
    Trie() {
        memset(children, 0, sizeof(children));
        finish = no = yes = 0;
    }
    ~Trie() {
        rep(i, MAXV) if (children[i]) delete children[i];
    }
    void insert(const char* key, bool rmv) {
        if (*key == 0) {
            if (rmv) finish = true;
            return;
        }
        else {
            int nxt = conv(*key);
            if (!children[nxt]) children[nxt] = new Trie;
            if (rmv) children[nxt]->yes = true;
            else children[nxt]->no = true;
            children[nxt]->insert(key + 1, rmv);
        }
    }
    int solve(bool rt) {
        int ret = 0;
        rep(i, MAXV) {
            if (children[i]) {
                if (children[i]->yes && children[i]->no) {
                    ret += children[i]->solve(0);
                    if (children[i]->finish) ret += 1;
                }
                else if(children[i]->yes)
                    ++ret;
            }
        }
        return ret;
    }
};


int main() {
    FAST;
    cin >> tc;
    REP(i,tc) {
        Trie* root = new Trie;
        cin >> A;
        rep(j,A) {		
            cin >> s;
            root->insert(s.c_str(), 1);
        }
        cin >> B;
        rep(j,B) {
            cin >> s;
            root->insert(s.c_str(), 0);
        }
        int ans = root->solve(1);
        if (!B) ans = 1;
        cout << ans << '\n';
        delete root;
    }
    return 0;
}