트라이 (Trie)

여러 문자열을 저장하는 자료구조이다.

래딕스 트리(radix tree), 접두사 트리(prefix tree)라고도 한다.

코드

#include <stdio.h>
#include <memory.h>

struct Trie {
    bool finish;
    Trie *next[26];

    Trie() : finish(false) {
        memset(next, 0, sizeof(next));
    }
    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (next[i])
                delete next[i];
    }
    void insert(const char *key) {
        if (*key == '\0')
            finish = true;
        else {
            int curr = *key - 'a';
            if (next[curr] == NULL)
                next[curr] = new Trie();
            next[curr]->insert(key + 1);
        }
    }
    Trie *find(const char *key) {
        if (*key == '\0')
            return this;
        int curr = *key - 'a';
        if (next[curr] == NULL)
            return NULL;
        return next[curr]->find(key + 1);
    }
};

int main()
{
    int n, m, result = 0;
    char s[501];
    Trie t;

    scanf("%d %d", &n, &m);
    while (n--) {
        scanf("%s", s);
        t.insert(s);
    }
    while (m--) {
        scanf("%s", s);
        Trie *ret = t.find(s);
        if (ret != NULL && ret->finish)
            result++;
    }

    printf("%d", result);

    return 0;
}

문자열 집합 소스 - https://www.acmicpc.net/problem/14425

정리

  • 오토마타를 트리처럼 나타낸 것이다. 각각의 state 와 accepted 상태의 노드를 final state 라고 한다.
    • he, she, her, him, show 가 있으면 아래와 같이 나타낼 수 있다
      • h
        • (e)
          • (r)
        • i
          • (m)
      • s
        • h
          • (e)
          • o
            • (w)
    • 찾을때 h->e->r 과 같이 찾는다.
  • 트라이 문제는 트라이를 그리고 규칙을 관찰하다보면 풀리는 경우가 많다.
  • 트라이 문제는 입력 데이터의 전체 글자 개수는 얼마를 넘지 않는다라는 식의 조건이 등장한다.
  • 공간복잡도는 26byte * 포인터크기 * 총 노드 수가 필요하다.
  • 트라이에 문자열을 삽입, 탐색에 걸리는 시간은 문자열의 길이이다.

관련 문제

  • 14425 : 문자열집합
  • 5052 : 전화번호 목록
  • 4358 : Hardwood Species
  • 5670 : Cellphone Typing ★
  • 3979 : 아름다운 이름 ★
  • 5446 : The Great Cleanup ★

참고 자료

results matching ""

    No results matching ""