접미사 배열(Suffix Array)과 LCP(Longest Common Prefix)

 

개인적으로 알고리즘은 즉각적으로 바로 구현할 수 있도록 몸에 베어야 하되 복습하는 데 너무나 많은 시간을 투자해서는 안 되고, 문제를 풀면서 실전으로 익혀야 한다고 생각한다. 학기가 시작되면서 바빠진 만큼 지난 잊힌 알고리즘 개념들을 핵심과 코드만 짧게 정리하여 평소에도 자주 보면서 익숙해지고자 한다. 기본적으로 코드는 특별한 설명이 없으면 C++를 기반으로 한다.

 

 

 

접미사 배열(Suffix)

 

정의

 

문자열 $S$의 모든 접미사들을 사전 순으로 정렬한 배열.

여기서 접미사들은 문자열 $S$에서 시작 위치 번호로 관리한다.

 

 

문제

 

문자열 $S$="abcbca"의 접미사 배열을 구해보자.

 

접미사: "abcbca", "bcbca", "cbca", "bca", "ca", "a"

사전 순으로 정렬 시 "a", "abcbca", "bca", "bcbca", "ca", "cbca"

 

문자열 길이가 $N$일 때, 일일이 접미사 문자열을 비교하면서 사전 순으로 정렬하려면?

집미사 사전 순 정렬 시: $O(N\log N)$

각 접미사마다 문자열 일일이 비교: $O(N)$

 

$O(N\log N)\times O(N)=O(N^2\log N)$ → 시간복잡도를 줄일 수는 없을까?

 

핵심은 문자열 $S$의 접미사의 접두사는 $S$의 부분 문자열임을 이용한다.

 

 

 

$O(N\log N^2)$ 방법

 

 

LCP(Longest Common Prefix)

 

사전 순으로 정렬한 접미사 배열에서 인접한 접미사끼리 최대로 겹치는 접두사의 길이

 

 

예시

 

$S$ = "abcbca"의 접미사 배열을 사전 순으로 정렬하기

그룹 번호로 정렬된 인접한 두 접미사의 접두사를 길이 1, 2, 4, 8, $\dots$ 처럼 $2^i$ 만큼씩 비교하며 정렬해 가는데, 새롭게 정렬한 순서가 새로운 그룹 번호가 된다.

 

빈 문자열 " "을 0으로 시작하여, abcbca", "bcbca", "cbca", "bca", "ca", "a"에 각각 접미사 번호가 1부터 6까지 붙어 있다고 가정한다.

즉, 빈 문자열을 제외한 접미사의 시작 위치가 문자열에서 몇 번째 문자부터 시작하는지 그 위치대로 접미사 번호가 붙는다고 가정한다.

 

 

(1)

	" "	abcbca	a	bcbca	bca	cbca	ca
접미사 번호	6	0	5	1	3	2	4
그룹 번호	-1	0	0	1	1	2	2

 

길이 1만큼의 접두사끼리만 비교해서 사전 순으로 그룹 번호를 부여한다.

동일한 접두사를 지니면 같은 그룹 번호를 부여한다.

처음에는 길이 1만큼의 접두사를 비교하므로 결국 접미사의 맨 앞 문자의 사전순으로 그룹 번호를 부여한다고 생각해도 되며, 실제 코드로 구현할 때도 접미사의 맨 앞 문자 기준으로 정렬하면 된다.

 

 

(2) 

 

	" "	a	abcbca	bcbca	bca	ca	cbca
접미사 번호	6	5	0	1	3	4	2
그룹 번호	-1	0	1	2	2	3	4

 

이전 그룹 번호로 정렬된 상태에서 인접한 두 접미사의 길이 2만큼의 접두사끼리 비교해서 새로 정렬한 후 그룹 번호를 부여한다.

a와 abcbca의 비교에서 a 뒤의 문자열은 비어 있는데, 빈 문자열에 관한 우선순위는 가장 높으므로 a의 그룹 번호가 더 작게 된다.

 

 

(3)

 

마찬가지로 이전 그룹 번호 기준으로 정렬된 상태에서 인접한 두 접미사의 길이 4만큼의 접두사끼리 비교하여 새로 정렬한 후 그룹 번호를 부여한다.

 

 

이를 일반화하면 다음과 같이 정리할 수 있다.

 

길이 2K만큼의 접두사끼리 비교하는 경우

(1)  두 접미사에서 길이 K만큼의 접두사를 비교한다.

(2) 같은 접두사를 지니면 뒤의 길이 K만큼의 부분 문자열을 비교한다.

 

 

 

 

코드

 

suffix_array[i]: 접미사 배열에서 $i$번째 위치한 원소가 문자열에서 어느 위치에서 시작하는 접미사인지 그 위치 (접미사 번호)

 

group[i][j]: 접미사 배열을 완성하기 위해 정렬 과정에서 필요한 배열 (길이에 대응되는 level i에 따른 그룹 번호 j)

 

vector<int> suffix_array(n);
vector<vector<int>> group(G_MAX, vector<int>(n+1));

int checkCount(int i, int j, int k, int n){
	int cnt = 0;
    while (i < n && j < n && k >= 0){
    	cnt += (1 << k);
        i += (1 << k);
        j += (1 << k);
    }
}

// 배열 초기화
for (int i = 0; i < n; i++){
    suffix_array[i] = i;
    group[0][i] = s[i];
}

group[0][n] = -1;

int last = 0;

for (int k = 0, len = 1; len / 2 < n; k++, len *= 2){
	auto cmp = [&](int u, int v){
    	if (group[k][u] == group[k][v]){
        	return group[k][u + len] < group[k][v + len];
        }
        else {
        	return group[k][u] < group[k][v];
       	}
    };
    
    sort(suffix_array.begin(), suffix_array.end(), cmp);
    
    last = k + 1;
    
    group[last][suffix_array[0]] = 0;
    
    for (int i = 1; i < n; i++){
    	if (cmp(suffix_array[i - 1], suffix_array[i])){
        	group[last][suffix_array[i]] = group[last][suffix_array[i - 1]] + 1;
        }
        else {
        	group[last][suffix_array[i]] = group[last][suffix_array[i - 1]];
        }
    }
    group[last][n] = -1;
}