카사이의 알고리즘(Kasai's Algorithm)은 접미사 배열(Suffix Array)을 이용해 최장 공통 접두사(Longest Common Prefix, LCP) 배열을 선형 시간에 계산하는 효율적인 알고리즘입니다. 먼저 문자열의 접미사 배열을 구한 뒤, 카사이의 알고리즘이 이 접미사 배열을 입력받아 LCP 배열을 생성합니다.
일반적인 방식으로 LCP를 계산하면 O(m log n)의 시간이 소요됩니다(여기서 m은 패턴 길이, n은 텍스트 길이). 반면 카사이의 알고리즘은 O(n)의 선형 시간 복잡도로 작동하기 때문에 대용량 텍스트에서도 매우 빠른 성능을 보여줍니다.
동작 원리 이해하기: "banana" 예시
문자열 "banana"의 모든 접미사를 나열하고 사전순으로 정렬하면 다음과 같습니다.
- a → 인덱스 5
- ana → 인덱스 3
- anana → 인덱스 1
- banana → 인덱스 0
- na → 인덱스 4
- nana → 인덱스 2
정렬된 순서대로 시작 인덱스를 나열한 것이 접미사 배열 [5, 3, 1, 0, 4, 2]입니다. 그리고 인접한 두 접미사 간의 공통 접두사 길이를 기록한 것이 LCP 배열 [1, 3, 0, 0, 2, 0]입니다. 예를 들어 "a"와 "ana"의 공통 접두사는 "a"로 길이가 1이며, "ana"와 "anana"의 공통 접두사는 "ana"로 길이가 3입니다.
입력과 출력
입력: 메인 문자열: "banana" 출력: 접미사 배열(Suffix Array): 5 3 1 0 4 2 공통 접두사 배열(LCP Array): 1 3 0 0 2 0
알고리즘
1단계: buildSuffixArray(text) — 접미사 배열 생성
입력: 메인 문자열
출력: 메인 텍스트로부터 구성된 접미사 배열
이 함수는 랭킹(rank) 쌍을 활용해 접미사들을 점진적으로 정렬합니다. 처음에는 앞 2글자를 기준으로 정렬하고, 이후 k를 2배씩 늘려가며 앞 4글자, 8글자… 순으로 확장해 나가므로 전체 시간 복잡도는 O(n log n)입니다.
Begin
n := size of text
for i := 0 to n, do
suffArray[i].index := i
suffArray[i].rank[0] := text[i]
if (i+1) < n, then
suffArray[i].rank[1] := text[i+1]
else
suffArray[i].rank[1] := -1
do
sort the suffix array
define index array to store indexes
for k := 4 to (2*n)-1, increase k by k*2, do
currRank := 0
prevRank := suffArray[0].rank[0]
suffArray[0].rank[0] := currRank
index[suffArray[0].index] = 0
for all character index i of text, do
if suffArray[i].rank[0] = prevRank AND suffArray[i].rank[1] =
suffArray[i-1].rank[1], then
prevRank := suffArray[i].rank[0]
suffArray[i].rank[0] := currRank
else
prevRank := suffArray[i].rank[0]
suffArray[i].rank[0] := currRank + 1
currRank := currRank + 1
index[suffArray[i].index] := i
done
for all character index i of text, do
nextIndex := suffArray[i].index + k/2
if nextIndex< n, then
suffArray[i].rank[1] := suffArray[index[nextIndex]].rank[0]
else
suffArray[i].rank[1] := -1
done
sort the suffArray
done
for all character index i of text, do
insert suffArray[i].index into suffVector
done
End
2단계: kasaiAlgorithm(text, suffVector) — LCP 배열 계산
입력 − 메인 텍스트와 접미사 목록(suffVector)
출력: 최장 공통 접두사가 계산된 LCP 배열
핵심 아이디어는 역접미사 배열(suffixInverse)을 만들어 원본 문자열의 위치에서 접미사 배열 내 순위를 즉시 찾을 수 있게 하는 것입니다. 또한 이전 단계에서 계산한 공통 접두사 길이 k를 재활용하기 때문에 전체 반복 횟수가 O(n)으로 제한됩니다.
Begin
n := size of suffVector
define longPrefix list of size n and fill all entries with 0
define suffInverse list of size n and fill all entries with 0
for all index values 'i' of suffVector, do
suffInverse[suffVector[i]] = i
done
k := 0
for i := 0 to n-1, do
if suffInverse[i] = n-1 then
k := 0
ignore the bottom part and go for next iteration.
j := suffVector[suffInverse[i]+1]
while (i+k)<n AND (j+k) < n and text[i+k] = text[j+k], do
increase k by 1
done
longPrefix[suffInverse[i]] := k
if k > 0 then
decrease k by 1
done
return longPrefix
End
예제 코드 (C++)
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct suffix {
int index;
int rank[2]; // 랭크 쌍 저장
};
bool compare(suffix s1, suffix s2) { // sort 함수용 접미사 비교
if(s1.rank[0] == s2.rank[0]) {
if(s1.rank[1] < s2.rank[1])
return true;
else
return false;
}else {
if(s1.rank[0] < s2.rank[0])
return true;
else
return false;
}
}
vector<int> buildSuffixArray(string mainString) {
int n = mainString.size();
suffix suffixArray[n];
for (int i = 0; i < n; i++) {
suffixArray[i].index = i;
suffixArray[i].rank[0] = mainString[i] - 'a'; // 기존 랭크 저장
suffixArray[i].rank[1] = ((i+1)<n)?(mainString[i+1]-'a'):-1; // 알파벳 순 정렬 후 랭크
}
sort(suffixArray, suffixArray+n, compare); // 앞 2글자 기준 정렬
int index[n]; // suffixArray 내 인덱스
for (int k = 4; k < 2*n; k = k*2) { // k를 2의 거듭제곱으로 증가
int currRank = 0;
int prevRank = suffixArray[0].rank[0];
suffixArray[0].rank[0] = currRank;
index[suffixArray[0].index] = 0;
for (int i = 1; i < n; i++) { // 모든 접미사에 랭크 부여
if (suffixArray[i].rank[0] == prevRank && suffixArray[i].rank[1] == suffixArray[i-1].rank[1]) {
prevRank = suffixArray[i].rank[0];
suffixArray[i].rank[0] = currRank;
}else{ // 랭크 증가 후 할당
prevRank = suffixArray[i].rank[0];
suffixArray[i].rank[0] = ++currRank;
}
index[suffixArray[i].index] = i;
}
for (int i = 0; i < n; i++) { // 모든 접미사에 다음 랭크 할당
int nextIndex = suffixArray[i].index + k/2;
suffixArray[i].rank[1] = (nextIndex < n)? suffixArray[index[nextIndex]].rank[0]: -1;
}
sort(suffixArray, suffixArray+n, compare); // 앞 k글자까지 정렬
}
vector<int>suffixVector;
for (int i = 0; i < n; i++)
suffixVector.push_back(suffixArray[i].index); // 모든 접미사 인덱스를 벡터에 저장
return suffixVector;
}
vector<int> kasaiAlgorithm(string mainString, vector<int> suffixVector) {
int n = suffixVector.size();
vector<int> longPrefix(n, 0); // 크기 n, 0으로 초기화
vector<int> suffixInverse(n, 0);
for (int i=0; i < n; i++)
suffixInverse[suffixVector[i]] = i; // 역접미사 배열 값 채우기
int k = 0;
for (int i=0; i<n; i++) { // 메인 문자열의 모든 접미사 처리
if (suffixInverse[i] == n-1) { // 위치 (n-1)의 접미사인 경우
k = 0;
continue;
}
int j = suffixVector[suffixInverse[i]+1]; // 접미사 목록의 다음 문자열
while (i+k<n && j+k<n && mainString[i+k]==mainString[j+k]) // k번째 인덱스부터 비교
k++;
longPrefix[suffixInverse[i]] = k; // 현재 접미사의 접두사 길이
if (k>0)
k--; // 문자열의 첫 글자 제거
}
return longPrefix;
}
void showArray(vector<int> vec) {
vector<int>::iterator it;
for (it = vec.begin(); it < vec.end() ; it++)
cout << *it << " ";
cout << endl;
}
int main() {
string mainString = "banana";
vector<int>suffixArray = buildSuffixArray(mainString);
int n = suffixArray.size();
cout<< "Suffix Array : "<<endl;
showArray(suffixArray);
vector<int>commonPrefix = kasaiAlgorithm(mainString, suffixArray);
cout<< "\nCommon Prefix Array : "<<endl;
showArray(commonPrefix);
}
실행 결과
Suffix Array : 5 3 1 0 4 2 Common Prefix Array : 1 3 0 0 2 0
마무리
카사이의 알고리즘은 접미사 배열만 있다면 LCP 배열을 추가 비용 없이 거의 선형 시간에 얻을 수 있는 강력한 도구입니다. LCP 배열은 문자열 검색 최적화, 반복 패턴 탐지, 최장 반복 부분 문자열 찾기 등 다양한 문자열 처리 문제의 핵심 요소로 활용되므로, 접미사 배열 기반 알고리즘을 학습할 때 반드시 함께 익혀두는 것이 좋습니다.