ITPE * JackerLab

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

개요LCP Array는 문자열의 접미사(Suffix)들을 사전순으로 정렬한 Suffix Array에 대해, 인접한 접미사들 간의 최장 공통 접두사(Longest Common Prefix) 길이를 저장하는 배열입니다. 문자열 검색, 패턴 매칭, 중복 탐지, 데이터 압축 등 다양한 분야에서 핵심적인 역할을 하며, Suffix Array와 함께 문자열 인덱싱 및 분석의 효율을 극대화합니다.1. 개념 및 정의 항목 내용 정의Suffix Array 상에서 인접한 두 접미사 간 최장 공통 접두사 길이를 저장한 배열목적빠른 문자열 매칭, 중복 탐색, 최장 반복 문자열 분석필요성Suffix Array 단독으로는 접미사 간 유사성 판단이 어려움LCP Array는 문자열 구조를 더 깊이 이해하고 빠르게 비교하기 위해 필..

개요Suffix Array는 문자열의 모든 접미사(suffix)를 사전 순으로 정렬한 후, 해당 접미사들의 시작 위치를 배열로 저장한 자료구조입니다. 주로 문자열 검색, 패턴 매칭, 중복 탐색, 데이터 압축 분야에서 활용되며, Suffix Tree에 비해 메모리 사용이 적고 구현이 간단해 실용성이 뛰어납니다.1. 개념 및 정의 항목 내용 정의문자열의 모든 접미사를 정렬하고 그 시작 인덱스를 저장하는 배열 자료구조목적빠르고 효율적인 문자열 검색 및 패턴 매칭 지원필요성대용량 문자열 데이터 처리 시 빠른 탐색 및 비교 성능 확보Suffix Array는 Suffix Tree보다 구현이 쉽고 메모리 소모가 적어 대규모 데이터 처리에 적합합니다.2. 특징항목Suffix Array의 특징유사 개념 비교메모리 효율..