트라이

[알고리즘] 트라이(Trie) 트라이(TRIE) 트라이(TRIE)retrieval 문자열의 집합을 표현하는 트리를 말한다모든 문자열은 다른 문자열의 접두어가 아니라고 가정 부분 문자열 검사ba가 abac의 부분 문자열인가?두개 접두사의 최장 공통 접두어 찾기abac와 ac의 최장 공통 접두어는?사전적 순서로 정렬된 k번째 접미사 찾기abac의 3번째 접미사는? : abac, ac, bac, c (정답 : bac) 각 간선은 하나의 문자에 대응한다같은 노드에 나오는 간선들은 같은 레벨을 갖지 않음각 문자열은 단말 노드에 대응한다 Compressed Trie노드들과 간선들을 부분 문자열로 압축(= 접미어 트리(Suffix Tree)) 문자열 S = {xabxac}에 대한 접미어 트리 발생하는 문제점 해결책하..