ITPE * JackerLab

개요Suffix Automaton(접미사 오토마톤)은 문자열 내의 모든 부분 문자열(substring)을 표현할 수 있는 최소한의 결정적 유한 상태 기계(Deterministic Finite Automaton, DFA)이다. 특히 문자열 탐색, 패턴 매칭, 중복 서브스트링 계산 등에서 뛰어난 성능을 발휘하며, 알고리즘 대회 및 컴파일러, 생물정보학 등의 분야에서 널리 활용된다.1. 개념 및 정의Suffix Automaton은 주어진 문자열의 모든 접미사 및 부분 문자열을 상태와 전이로 표현하여, 빠른 문자열 탐색 및 비교 연산을 가능하게 하는 자료구조이다.목적: O(n) 시간 복잡도로 substring 쿼리 처리 가능필요성: 패턴 검색, 중복 검출 등에서 Trie나 Suffix Tree 대비 공간 효율성..

개요Wavelet Tree는 **문자열이나 시퀀스에서 순위(rank), 선택(select), 구간 빈도(range frequency)**와 같은 질의를 빠르게 처리할 수 있도록 설계된 이진 트리 기반의 압축 인덱스 자료구조입니다. 본래 압축 텍스트 인덱싱을 위해 개발되었으나, 현재는 생물정보학, 정보 검색, 문자열 알고리즘 등 다양한 분야에서 활용되고 있습니다.1. 개념 및 정의Wavelet Tree는 입력 시퀀스를 여러 레벨의 이진 트리로 분해하고, 각 노드에 비트 벡터를 저장하여 특정 질의를 O(log σ) 시간에 처리할 수 있도록 구성됩니다.입력: 길이 n의 시퀀스 S over alphabet Σ트리 구조: 알파벳 구간을 기준으로 분할된 이진 트리노드 데이터: 현재 구간 내 요소의 분할 여부를 나타..