Suffix Tree/Array

Suffix Tree/Array

문자열의 모든 접미사(Suffix)를 효율적으로 저장하고 검색하기 위한 자료구조로, Suffix Tree는 압축된 트라이, Suffix Array는 정렬된 접미사 인덱스 배열로 패턴 매칭과 문자열 분석을 O(m) 또는 O(m log n) 시간에 수행

목적: 고속 패턴 매칭, 문자열 검색, 최장 공통 부분 문자열, DNA 서열 분석

Suffix Tree 특징: 압축 트라이, 선형 공간 O(n), 선형 구축 O(n), 패턴 매칭 O(m)

Suffix Array 특징: 정렬된 접미사 시작 위치, O(n) 공간, 구축 O(n log n), 검색 O(m log n) + LCP 배열 활용

구성요소: Suffix Tree(내부 노드, 간선 라벨, 리프 노드), Suffix Array(정렬 인덱스 배열, LCP 배열)

주요 연산: 패턴 매칭, 최장 반복 부분 문자열, 최장 공통 부분 문자열, 문자열 압축

시간 복잡도: Suffix Tree(구축 O(n)/검색 O(m)), Suffix Array(구축 O(n log n)/검색 O(m log n))

공간 복잡도: Suffix Tree O(n) 실제 20n, Suffix Array O(n) 실제 4n

장점: 고속 패턴 매칭, 다양한 문자열 쿼리, 선형 시간 구축(Suffix Tree)

단점: 구현 복잡도(Suffix Tree), 높은 메모리(Suffix Tree), 구축 느림(Suffix Array)

적용사례: DNA 서열 분석, 텍스트 압축(LZ77, BWT), 검색 엔진, 표절 검사, 문자열 유사도

비교: Suffix Tree(빠름/메모리 많음) vs Suffix Array(느림/메모리 적음) vs 트라이(단순/메모리 많음)

연관: 트라이, 패턴 매칭, LCP 배열, Burrows-Wheeler Transform