트라이 기초

트라이

문자열 검색을 빠르게 실행할 수 있도록

설계한 트리 형태 자료구조

 

특징

1. N진 트리

문자 종류의 개수에 따라 N이 결정

알파벳은 26개의 문자 -> 26진 트리

2. 루트 노드는 항상 빈 문자열을 뜻하는 

공백 상태를 유지

 

 

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

14425번: 문자열 집합

해시 테이블로 풀었던 문제다.

트라이로 풀어보자.

좋은 코드는 아니다. 시간 엄청 걸린다.

 

<트라이 자료구조 만들기>

현재 문자열을 가리키는 위치의 노드가

공백 상태면 신규 노드를 생성

아니라면 이동.

문자열의 마지막에 도달하면 리프 노드 표시

 

탐색

집합 S에 포함된 문자열을 센다.

문자열이 끝날 때까지 공백 상태가 없고

마지막 노드가 트라이의 리프 노드라면

집합 S에 포함된 문자열

 

Node라는 클래스를 만들자

생성자

Node() : isEnd(false) {
         fill(next, next + 26, nullptr);
}

 

소멸자

클래스안의 "동적으로 할당된 멤버변수"가 있다면

소멸자안에 메모리를 풀어주는 코드를 넣어 주어야 한다!

 

~Node() {
for (auto& child : next)
         delete child;
}

 

메소드 -> insert, find

 

#include <iostream>
#include <algorithm>
using namespace std;
 
class Node {
 
public:
    Node* next[26];
    bool isEnd;
 
    Node() {
        isEnd = false;
        fill(next, next + 26, nullptr);
    }
 
    ~Node() {
        for (auto& child : next)
            delete child;
    }
 
    void insert(char* key)
    {
        if (*key == 0) // 문자열의 끝
            isEnd = true;
        else
        {
            int next_index = *key - 'a';
 
            if (next[next_index] == nullptr)
                next[next_index] = new Node();
 
            return next[next_index]->insert(key + 1);
        }
    }
 
    // 문자열 찾기 
    Node* find(const char* key)
    {
        // 문자열의 끝
        if (*key == 0)
            return this;
 
        int next_index = *key - 'a';
 
        if (next[next_index] == nullptr)
            return nullptr;
 
        return next[next_index]->find(key + 1);
    }
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, m;
    cin >> n >> m;
 
    // root는 공백이다.
    Node* root = new Node();
 
    while (n > 0)
    {
        char text[501];
        cin >> text;
        root->insert(text);
        n--;
    }
 
    int count = 0;
    while (m > 0)
    {
        char text[501];
        cin >> text;
        Node* result = root->find(text);
 
        if (result && result->isEnd)
            count++;
        m--;
    }
 
    cout << count << '\n';
}