Trie와 동적 Trie

코드의 기초는 

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

14425번: 문자열 집합

로 잡는다.

 

 

#include <iostream>
#define pii pair<int, int>
using namespace std;
 
int n, m;
 
class Trie
{
public :
    Trie* next[26];
    bool finish;
 
    Trie()
    {
        fill(next, next + 26, nullptr);
        finish = false;
    }
 
    ~Trie()
    {
        for (int i = 0; i < 26; i++)
        {
            if (next[i])
                delete next[i];
        }
    }
 
    void insert(char* str)
    {
        if (*str == '\0')
        {
            finish = true;
        }
        else
        {
            int su = *str - 'a';
 
            if (next[su] == NULL)
                next[su] = new Trie;
            next[su]->insert(str + 1);
        }
 
    }
 
    int search(char* str)
    {
        if (*str == '\0')
        {
            if (finish == true)
                return 1;
            else
                return 0;
        }
        int su = *str - 'a';
 
        if (next[su] == NULL)
            return 0;
 
        return next[su]->search(str + 1);
    }
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    cin >> n >> m;
    char str[510];
    Trie* root = new Trie;
 
    for (int i = 0; i < n; i++)
    {
        cin >> str;
        root->insert(str);
    }
 
    int ans = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> str;
        ans+= root->search(str);
    }
 
    cout << ans;
    delete root; // TC 가 걸리는 기준으로 매우 조심해야 ㅏㄴ다.
}
 

근데 풀다보니 동적 Trie 라는것도 있댄다....

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

3080번: 아름다운 이름

이 문제를 풀기 시작하면서 정적 Trie 보단 동적 Trie를 주시하게 되었다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
 
class Trie
{
public :
    vector<pair<int, Trie*>> next;
    int size;
    bool finish;
 
    Trie()
    {
        finish = false;
        size = 0;
    }
 
    void insert(char* str)
    {
        if (*str == 0)
        {
            finish = true;
            return;
        }
        int su = (int)(*str);
        for (int i = 0; i < size; i++)
        {
            if (next[i].first == su)
            {
                next[i].second->insert(str + 1);
                return;
            }
        }
        next.push_back({(int)(*str), new Trie});
        size++;
        next[size - 1].second->insert(str + 1);
    }
 
    int go(char* str)
    {
        if (*str == 0 && finish == true)
        {
            if (finish == true)
                return 1;
            else
                return 0;
        }
        int su = (int)(*str);
        for (int i = 0; i < size; i++)
        {
            if (next[i].first == su)
                return next[i].second->go(str + 1);
        }
        return 0;
 
    }
 
 
};
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int n, m;
 
    cin >> n >> m;
    Trie* root = new Trie;
 
    char str[502];
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> str;
        root->insert(str);
    }
    for (int i = 0; i < m; i++)
    {
        cin >> str;
        ans += root->go(str);
    }
    cout << ans;
 
}