접미사 배열 시각화
문자열의 모든 접미사를 정렬하고 LCP(최장 공통 접두사)를 분석하는 과정을 학습하세요
문자열★★★
속도
1 / 1현재 단계: -SA 크기: 0매칭 수: -
프리셋
각 단계를 클릭하면 해당 시점으로 이동합니다.
빌드 버튼을 눌러 시작하세요.
접미사 배열이란?
문자열의 모든 접미사를 사전순으로 정렬한 인덱스 배열입니다. 접미사 트리보다 메모리 효율적이면서 동일한 문제를 풀 수 있습니다.
사용 방법
- 1문자열을 입력하고 빌드하면 접미사 배열과 LCP 배열이 생성됩니다
- 2정렬 과정에서 접미사들의 순서 변화를 관찰하세요
- 3패턴 검색으로 이진탐색 기반 매칭을 확인하세요
- 4LCP 배열의 패턴을 분석해보세요
동작 원리
- 1모든 접미사의 시작 인덱스를 사전순으로 정렬합니다
- 2O(n log²n) 또는 SA-IS O(n) 알고리즘으로 효율적 구축
- 3LCP 배열: 인접 접미사 간 공통 접두사 길이, Kasai 알고리즘으로 O(n)에 계산
- 4패턴 검색: 이진탐색으로 O(m log n)에 수행
실무 활용
- •생물정보학 — 유전체 서열의 반복 패턴 검색
- •데이터 압축(BWT/bzip2)의 핵심 전처리
- •Full-text 검색 인덱스 구축
- •문자열 유사도/반복 구간 분석
비슷한 알고리즘
- •접미사 트리 — O(n) 구축, 더 강력하나 메모리 20배 이상 사용
- •트라이 — 여러 문자열의 접두사 검색에 적합, 단일 문자열에는 접미사 배열이 효율적
- •FM-index — 접미사 배열 + BWT 기반, 압축 인덱스로 메모리 절약
학습 팁
- •짧은 문자열(5~8자)로 접미사를 직접 나열하고 정렬해보세요
- •LCP 배열에서 반복 부분 문자열을 찾는 방법을 연습하세요
- •이진탐색으로 패턴을 찾는 과정을 손으로 추적해보세요
자주 묻는 질문
Q. 접미사 트리보다 좋은가?
A. 메모리 효율이 월등히 좋고 실용적입니다. 기능상 접미사 트리와 동등하며, LCP 배열을 함께 사용합니다.
Q. 구축 시간은?
A. SA-IS 알고리즘으로 O(n)에 가능하지만, O(n log²n) 방법이 더 직관적입니다.