트라이

여러 문자열을 저장하는 자료구조인 트라이(Trie)에 대해 알아봅시다.

 

문자열 집합 { "ab", "abc", "acd", "bcd", "be"} 가 있다고 할 때, 트라이는 문자열을 다음과 같은 트리로 저장합니다.

 

'$' : 루트노드

 

문자열을 트라이에 저장하면 루트 노드에서부터 시작해서, 앞에서부터 한 글자씩 해당하는 자식노드를 따라가게 됩니다.

문자열을 모두 저장했다면, 현재 노드에 저장된 문자열이 있다는 표시를 해 주면 됩니다. (그림에서 짙은 노드)

 

시간복잡도는 문자열 삽입에 \(O(L)\), 탐색에 \(O(L)\)입니다. (\(L\) : 문자열의 길이)

 

문자열을 set등의 BST로 저장하는 것보다 삽입, 탐색이 훨씬 빠르고,

해싱으로 저장했을 때의 충돌이 없기 때문에 안정적으로 문자열을 찾고 저장할 수 있습니다.

 

또, 자료구조 특성상 저장한 문자열의 접두사(prefix)에 관한 문제를 풀 때에도 요긴하게 사용할 수 있습니다.

 

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

14425번: 문자열 집합

이 문제를 트라이로 풀어봅시다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
 
struct Node
{
    bool exist = 0; // 현재 노드에 저장된 문자열 존재 여부
    Node* child[26] = { 0, };
    // 자식 노드들을 저장하는 포인터 배열
    // 경우에 따라 vector이나 set등을 사용할 수도 있다.
} *Trie;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    Trie = new Node;
 
    cin >> n >> m;
    while (n--)
    {
        string s; cin >> s;
        Node* curNode = Trie;
 
        for (char c : s)
        {
            int idx = c - 'a';
            if (!curNode->child[idx]) curNode->child[idx] = new Node;
            curNode = curNode->child[idx];
        }
 
        curNode->exist = true;
    }
 
    int ans = 0;
    while (m--)
    {
        string s; cin >> s;
        Node* curNode = Trie;
 
        bool flag = false;
        for (char c : s)
        {
            int idx = c - 'a';
            if (!curNode->child[idx])
            {
                flag = true;
                break;
            }
 
            curNode = curNode->child[idx];
        }
 
        if (!flag && curNode->exist) ans++;
    }
 
    cout << ans;
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217