ITPE * JackerLab

개요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의 한 접미사를 나타냄리프 노드는 문자열의 각 접미사의 시작 인덱스를 저장내부 노드는 공통 접두사를 공유하는 부분 문자열을 표현※ ..