ITPE * JackerLab

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

개요Ukkonen 알고리즘은 1995년 Esko Ukkonen이 발표한 문자열 전처리 알고리즘으로, O(n) 시간 복잡도에 문자열의 **Suffix Tree(접미사 트리)**를 구축할 수 있는 효율적인 방법입니다. 이는 이전의 O(n²) 또는 O(n log n) 시간 복잡도를 갖는 방법들보다 획기적으로 빠르며, 특히 온라인(online) 방식으로 입력 문자열을 한 글자씩 읽으며 트리를 갱신할 수 있는 특징을 갖습니다.1. 개념 및 정의Ukkonen 알고리즘은 문자열 S의 접미사 트리를 점진적으로 구성하되, 접미사별로 전체 트리를 새로 만드는 것이 아니라, 공통 접두사를 재사용하며 **접미사 링크(Suffix Link)**와 지연 갱신(Lazy Update) 등의 기술로 효율성을 확보합니다.핵심 아이디어:..

개요Suffix Tree(접미사 트리)는 문자열의 모든 접미사(suffix)를 트리 형태로 표현한 자료구조로, 문자열 검색, 부분 문자열 탐색, 반복 패턴 찾기 등 다양한 텍스트 알고리즘 문제를 O(m) 또는 **O(n)**의 시간 복잡도로 해결할 수 있도록 지원합니다. 특히 생물정보학, 텍스트 편집기, 데이터 압축 등 빠른 문자열 탐색이 필요한 분야에서 필수적인 자료구조입니다.1. 개념 및 정의Suffix Tree는 문자열 S의 모든 접미사를 루트에서부터 하위 노드로 이어지는 경로로 표현한 트라이(Trie) 기반의 압축 트리입니다. 다음과 같은 특징을 가집니다:각 경로는 S의 한 접미사를 나타냄리프 노드는 문자열의 각 접미사의 시작 인덱스를 저장내부 노드는 공통 접두사를 공유하는 부분 문자열을 표현※ ..

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