0. 개요

1) 특징

• 문자열을 효율적으로 저장 및 탐색하기 위한 트리 형태의 자료구조
  - 간선 : 문자 하나 / 루트노드~엣지노드 경로 : 전체 문자열 (retrieval)
  - 실무에서 유용, 특히 NLP에서 문자열 탐색 위한 자료구조로 널리 사용
  - ex. 자동완성 기능, 사전 검색 등

2) 종류

2-A. 트라이

2-B. 접미어 트라이

a) 개념 : 문자열의 모든 접미어를 Trie로 표현

길이가 n인 문자열 $A = a_0, a_1, a_2, ..., a_{n-1}$
$A = a_ia_{i+1}a_{i+2}...a_{n-1}$인 n개의 접미어 (0$\leq$i$\leq$n-1)

b) 활용

• 부분 문자열 검사 : "ba"가 "abac"의 부분 문자열인가?
  - 루트에서부터 한 문자씩 대응되는 간선 따라가기
• 두 접미어의 최장 공통 접두어 찾기 : "abac"와 "ac"의 최장 공통 접두어는 무엇인가?
  - 두 접미어의 끝 글자에 대응하는 노드 선택
  - 가장 가까운 공통조상 찾기
  - 공통 접두어 만들기
• 사전적 순서로 정렬된 k번째 접미어 찾기 : "abac"에서 사전적 순서로 3번째 접미어는 무엇인가?
  - DFS를 통해 사전적 순서로 정렬
  - 생성된 문자열을 메모리에 저장하지 않고 인덱스 값만 저장 -> {0, 2, 1, 3}
  

1. 노드 및 간선

2. 구현