알고리즘 기술

Trie와 동적 Trie

헐랭미 2020. 8. 19. 11:08

코드의 기초는 

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

 

14425번: 문자열 집합

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.  다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어�

www.acmicpc.net

로 잡는다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#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 가 걸리는 기준으로 매우 조심해야 ㅏㄴ다.
}
 
 cs

 

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

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

 

3080번: 아름다운 이름

문제 상근 선생님은 학생들에게 번호를 붙여주려고 한다. 상근이는 미술 선생님이기 때문에, 이름의 순서도 아름다워야 한다고 생각한다. 따라서, 다음과 같은 규칙을 지켜서 번호를 정하려고 �

www.acmicpc.net

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

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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;
 
}
cs
저작자표시