Suffix Array (접미사 배열)

Suffix Array (접미사 배열)

문자열의 모든 접미사를 사전순으로 정렬한 인덱스 배열로, O(n log n) 시간에 구축하며 패턴 검색, LCP 계산, 문자열 분석에 활용되는 공간 효율적 자료구조

목적: 접미사 정렬, 빠른 패턴 검색, 문자열 분석, Suffix Tree 대체

특징: 공간 효율(O(n)), 정렬 기반, 이진 검색 가능, LCP 배열 동반

구축 방법

• •Naive: 모든 접미사 정렬, O(n² log n)
• •Manber-Myers: 배수 길이 접두사 정렬, O(n log² n)
• •SA-IS: O(n) 선형 시간, 복잡한 구현

LCP 배열(Longest Common Prefix): 인접한 접미사의 최장 공통 접두사 길이, Kasai 알고리즘 O(n)

패턴 검색: 이진 검색으로 패턴의 범위 찾기, O(m log n), m=패턴 길이

시간 복잡도: 구축 O(n log n) ~ O(n), 검색 O(m log n)

공간 복잡도: O(n)

장점: 공간 효율(Suffix Tree 대비 상수 계수 작음, 실메모리 절약), 빠른 검색, 다양한 응용

단점: 구축 시간, 동적 갱신 어려움, 구현 복잡

적용사례: 문자열 검색, DNA 서열 분석, 데이터 압축(BWT), 텍스트 인덱싱, 최장 반복 부분 문자열

비교: Suffix Array(공간효율/O(n)/상수 작음) vs Suffix Tree(빠름/O(n)/상수 큼) vs Trie(접두사)

연관: Suffix Tree, LCP, 이진 검색, 문자열, BWT