접미사 배열과 LCP: 문자열 검색 및 분석의 최종 병기 가이드
문자열 내부에서 반복되는 패턴을 찾거나, 두 문자열의 공통 부분 문자열을 찾는 등 복잡한 문자열 문제는 단순히 KMP 알고리즘만으로는 해결하기 어려운 경우가 많습니다. 이때 강력한 힘을 발휘하는 자료구조가 바로 접미사 배열(Suffix Array)과 LCP(Longest Common Prefix) 배열입니다. 이들은 문자열의 모든 접미사를 사전순으로 정렬하여 구조화함으로써, 문자열 내 모든 부분 문자열에 대한 정보를 효율적으로 추출하게 해줍니다. 본 포스팅에서는 이들의 구축 원리와 응용법을 2,500자 이상의 기술적 분석으로 정리해 보겠습니다.
1. 접미사 배열(Suffix Array)의 정의와 가치
접미사 배열은 특정 문자열의 모든 접미사를 사전순으로 정렬한 뒤, 그 접미사들이 시작되는 원래의 인덱스를 저장한 배열입니다. 예를 들어 "banana"라는 문자열이 있다면, "banana", "anana", "nana", "ana", "na", "a"라는 6개의 접미사를 사전순으로 나열한 것입니다. 이 배열이 있으면 이분 탐색을 통해 특정 패턴이 문자열 내에 존재하는지 $O(M \log N)$ 시간 내에 찾아낼 수 있으며, 모든 부분 문자열에 대한 인덱싱이 완료된 것과 다름없습니다.
1-1. 왜 접미사 배열인가?
접미사 트리(Suffix Tree)라는 자료구조도 존재하지만, 구현이 매우 복잡하고 메모리 소모가 극심합니다. 반면 접미사 배열은 단순한 정수 배열 형태이므로 메모리 효율이 좋고, 최근의 알고리즘 대회나 실무 최적화 시스템에서는 접미사 배열과 LCP의 조합이 사실상의 표준으로 자리 잡았습니다.
2. 효율적인 접미사 배열 구축: Manber-Myers 알고리즘
단순하게 모든 접미사를 생성하고 정렬하면 $O(N^2 \log N)$의 시간이 걸려 매우 비효율적입니다. 하지만 접미사들 간의 관계를 이용하면 훨씬 빠르게 구축할 수 있습니다. 가장 대표적인 Manber-Myers 알고리즘은 접미사 배열의 랭킹 정보를 활용하여 $2^k$씩 길이를 늘려가며 정렬하는 방식(Doubling)을 취합니다.
2-1. Doubling 기법의 마법
처음에는 첫 글자만 보고 정렬하고, 다음에는 두 글자, 그 다음에는 네 글자를 기준으로 정렬합니다. 이때 이전 단계에서 정렬된 순위를 활용하여 두 부분의 순위 쌍(Pair)으로 정렬하기 때문에 $O(N \log^2 N)$ 혹은 $O(N \log N)$의 복잡도로 배열을 완성할 수 있습니다. 이는 수십만 자의 문자열도 수 초 내에 정렬할 수 있는 압도적인 성능입니다.
3. LCP(Longest Common Prefix) 배열의 역할과 가사이(Kasai) 알고리즘
접미사 배열만으로는 부족한 정보를 채워주는 것이 LCP 배열입니다. LCP 배열은 사전순으로 정렬된 접미사 배열에서 인접한 두 접미사 사이의 공통 접두사 길이를 저장합니다. 이를 통해 문자열 내의 중복된 패턴이나 가장 긴 반복 부분 문자열(Longest Repeated Substring) 등을 매우 빠르게 계산할 수 있습니다.
3-1. Kasai 알고리즘을 이용한 $O(N)$ 구축
LCP 배열을 일일이 비교하며 구하면 $O(N^2)$이 걸리지만, Kasai 알고리즘을 사용하면 $O(N)$ 만에 구할 수 있습니다. 문자열의 앞에서부터 순서대로 LCP 값을 구하되, 이전 단계의 LCP 값이 $H$라면 다음 단계의 LCP 값은 최소 $H-1$ 이상이라는 성질을 이용하여 중복 계산을 피하는 것이 핵심입니다.
4. 접미사 배열과 LCP의 실전 응용
이 자료구조 조합은 문자열 문제의 '끝판왕'이라 불립니다.
- 공통 부분 문자열 탐색: 두 문자열을 합친 뒤 접미사 배열을 만들어 가장 긴 공통 부분을 탐색합니다.
- 중복 패턴 분석: 데이터 압축 알고리즘에서 반복되는 문자열 구간을 찾아 효율을 높입니다.
- 유전자 서열 비교: 거대한 DNA 염기 서열 내에서 특정 염기 조합의 출현 빈도와 위치를 고속으로 인덱싱합니다.
1. 정의: 모든 접미사를 사전순으로 정렬하여 부분 문자열 탐색의 기반을 마련합니다.
2. 최적화: Doubling 기법과 Kasai 알고리즘을 통해 대규모 텍스트도 고속으로 처리합니다.
3. 용도: 가장 긴 반복 문자열 탐색, 텍스트 인덱싱, 바이오인포매틱스 분야의 필수 기술입니다.