Suffix Array & LCP Array(Longest Common Prefix Array)

Suffix Array는 번역하면 접미사 배열으로 다양한 문자열 문제들을 해결할 수 있는 매우 강력한 자료구조 입니다.

Suffix Array는 문자열의 Suffix를 사전순으로 정렬한 배열입니다.

예를 들어 banana라는 문자가 있다면 Suffix Array는 다음과 같이 됩니다.

하지만 Suffix Array를 이렇게 문자열로 가지고 있을 경우 O(N^2)의 공간 복잡도를 가지게 될 것입니다.

그렇기 때문에 Suffix Array는 몇번째 접미사인지 나타내는 정수 i만 가지는 정수형 자료 구조형태를 가집니다.

다음과 같이 말이죠.

자 이제 Suffix Array의 정의에 대해 알았으니 구현을 해 볼 차례입니다.

단순하게 접미사 배열을 구한다면 접미사를 구한다음 정렬을 하는 방법이 있겠군요

하지만 이 방법의 시간 복잡도는 O(N^2*logN)가 됩니다. [정렬 O(NlogN), 각각의 비교 O(N)]

하지만 대회에서 나오는 Suffix Array 문제를 해결하기에는 턱없이 큰 시간복잡도입니다.

좀 더 빠른 알고리즘을 생각해야겠군요.

접미사 배열을 구하는 알고리즘 중에는 무려 O(N)에 동작하는 알고리즘이 존재한다고는 합니다. 하지만 이는 너무 복잡하므로 PS에 사용되지는 않는다고 합니다.

따라서 저희가 사용해야 될 알고리즘은 O(N*(logN)^2)의 시간복잡도에 동작하는 Manber-Myers Algorithm이 되겠습니다.

Manber-Myers 알고리즘은 정렬하려는 문자열들이 모두 공통된 한 문자열의 접미사라는 점을 이용하여 

배열을 정렬할때 그 기준을 계속해서 바꾸는 방법으로 처음에는 첫글자 기준으로 정렬, 다음은 두글자 기준으로 정렬, 다음은 네글자.... 여덟글자.. 를 정렬합니다.

logN번의 정렬을 하기 때문에 O(N*(logN)^2)의 시간복잡도를 가집니다.

하지만 이런 방법으로 정렬을 해도 Suffix들을 비교할 때 O(N)이 걸린다고 생각할 수 있지만 이전에 정렬된 Suffix들을 이용하여 O(1)에 비교를 합니다.

우리는 현재 비교하는 기준이 되는 글자를 t번째 글자라고 할 때 현재 정렬 된 기준에서 t번째 글자가 같은 문자열 끼리 그룹으로 분류합니다. 위의 그림에서 명시적으로 보여주고 있군요.

우리는 t번째 글자에 대해서 정렬을 할 때 x번째 순서의 접미사와 y번째 순서의 접미사의 순서를 정한다면 그 처음 t글자의 그룹을 보면서 정렬을 하면 됩니다.

만약 그룹이 다르다면 자명하게 정렬이 가능합니다. 하지만 그룹이 같다면?

다음 t글자의 그룹을 보면됩니다. 왜냐하면 현재 글자에서 t글자 위에서 시작하는 접미사들을 t글자 기준으로 정렬되있기 때문이죠.

소스 코드를 보시면 조금 더 이해가 쉬우실겁니다. 바로 위에서 얘기한 비교 내용은 cmp함수를 보시면 되겠군요.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 500000
using namespace std;
char a[MAX_N];
int t, g[MAX_N], tg[MAX_N], SA[MAX_N];
bool cmp(int x, int y) {
    if (g[x] == g[y]) {
        return g[x + t] < g[y + t];
    }
    return g[x] < g[y];
}
void getSA(const char* str) {
    t = 1;
    int n = (int)strlen(str);    //글자의 수 배정
    for (int i = 0; i < n; i++) {        
        SA[i] = i;
        g[i] = str[i] - 'a';
    }        //첫 글자에 의한 그룹을 정해주는 전처리
    while (t <= n) {    //1,2,4,8... 씩 단어의 길이보다 작은 경우를 탐색
        g[n] = -1;
        sort(SA, SA + n, cmp);    //그룹에 의한 정렬
        tg[SA[0]] = 0;//다음 그룹을 할당하기 위하여 tempgroup의 첫번째 번호 배정
        for (int i = 1; i < n; i++) {    //다음 그룹 배정 
            if (cmp(SA[i - 1], SA[i])) //그룹이 다를 경우 다음 그룹 번호 할당
                tg[SA[i]] = tg[SA[i - 1]] + 1;
            else      //그룹이 같을 경우 같은 그룹 번호 할당
                tg[SA[i]] = tg[SA[i - 1]];
        }
        for (int i = 0; i < n; i++)
            g[i] = tg[i];    //새로운 그룹 할당
        t <<= 1;    
    }
}
int main() {
    scanf("%s", &a);
    getSA(a);
    for (int i = 0; i < strlen(a); i++)
        printf("%s\n", a + SA[i]);
    return 0;
}

자 이제 우리는 접미사 배열을 구하는 Manber-Myers Algorithm을 알게되었습니다.

우리는 어떠한 문제를 풀 수 있을까요?

예를 들자면 길이가 N인 환형 문자열에서 어떤 지점은 선택해 문자열을 읽을 때 이때 사전순으로 가장 앞서는 경우를 출력하는 문제가 있겠군요.

이러한 경우 문자열 두개를 붙인 문자열에서 Suffix Array를 구한 뒤 사전순으로 N보다 길거나 같으면서 가장 빠른 접미사의 앞에서 부터 N만큼만 출력하면 답이되는걸 알 수 있습니다.

하지만 우리는 더욱 더 많은 문제를 풀기 원하기 때문에 접미사 배열과 함께 자주 사용되는 LCP(Longest Common Prefix)를 알아보도록 하겠습니다.

LCP는 가장 긴 공통 접두사로 길이가 의미가 있는것입니다. 

LCP Array의 i번째 index 즉 LCP[I]는 Suffix Array의 i번째 접미사와 i-1번째 접미사의 가장 긴 공통 접두사의 길이로 정의됩니다.

LCP Array는 다음과 같이 채워지겠군요.

자 그러면 우리는 LCP Array를 어떻게 구할 수 있을까요?

가장 간단하게 생각할 수 있는 방법은 Suffix Array를 계산한 뒤 직접 비교를 하는 것입니다. 

하지만 이 방법은 O(N^2)의 시간 복잡도를 가지게 될 것입니다.

하지만 몇가지 아이디어를 이용하여 O(N)의 시간 복잡도에 LCP Array를 구할 수 있습니다.

O(N)의 시간 복잡도에 LCP를 구하기 위해서는 Suffix Array와 Suffix Array의 Inverse가 필요합니다.

S[i...]와 접미사 배열에서 인접한 접미사와의 LCP를 h라 할 때 h가 1보다 크면 S[i+1..]와 접미사 배열에서 인접한 접미사와의 LCP가 h-1 이상이라는 아이디어에 기반하여 구현되었는데 자세한 증명은 http://blog.naver.com/dark__nebula/220419358547에서 확인하시면 될 것 같습니다.

소스코드는 다음과 같습니다.

    for (int i = 0; i < n; i++)
        r[SA[i]] = i;
    int len = 0;
    for (int i = 0; i < n; i++) {
        int k = r[i];
        if (k) {
            int j = SA[k - 1];
            while (str[j + len] == str[i + len])
                len++;
            LCP[k] = len;
            if (len)
                len--;
        }
    }

LCP Array를 구현하는 시간복잡도는 O(N)이지만 전처리에 Suffix Array가 필요하기 때문에 결국 LCP Array의 시간복잡도는 Suffix Array의 시간복잡도에 지배받습니다.

우리는 Suffix Array를 통하여 어떤 문제들을 해결할 수 있을까요?

두번 이상 등장하는 부분문자열들에 대하여 효율적으로 계산 가능합니다.

->한 부분 문자열이 두번 이상 출현한다면 이를 접두사로 갖는 접미사들은 접미사 배열상에서 항상 인접해 있기 때문에 결국 LCP배열의 최대 길이와 두번 이상 등장하는 최대 부분 문자열은 동치가 됩니다.

두번 이상 등장하는 부문문자열의 종류나 한번만 등장하는 부분문자열 .. 두 문자열의 공통 부분 문자열 등.. 많은 문제를 활용 가능합니다.

끝으로 Suffix Array&LCP Array 기본 문제인 BOJ 9248 Suffix Array 소스 코드를 첨부하며 글을 마치겠습니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 600000
using namespace std;
char str[MAX_N];
int t, n, g[MAX_N], tg[MAX_N], SA[MAX_N], r[MAX_N], LCP[MAX_N];
bool cmp(int x, int y) {
    if (g[x] == g[y]) {
        return g[x + t] < g[y + t];
    }
    return g[x] < g[y];
}
int main() {
    scanf("%s", &str);
    t = 1;
    n = (int)strlen(str);    
    for (int i = 0; i < n; i++) {
        SA[i] = i;
        g[i] = str[i] - 'a';
    }        
    while (t <= n) {    
        g[n] = -1;
        sort(SA, SA + n, cmp);    
        tg[SA[0]] = 0;
        for (int i = 1; i < n; i++) {    
            if (cmp(SA[i - 1], SA[i]))
                tg[SA[i]] = tg[SA[i - 1]] + 1;
            else
                tg[SA[i]] = tg[SA[i - 1]];
        }
        for (int i = 0; i < n; i++)
            g[i] = tg[i];    
        t <<= 1;
    }
    for (int i = 0; i < n; i++)
        r[SA[i]] = i;
    int len = 0;
    for (int i = 0; i < n; i++) {
        int k = r[i];
        if (k) {
            int j = SA[k - 1];
            while (str[j + len] == str[i + len])
                len++;
            LCP[k] = len;
            if (len)
                len--;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d ", SA[i] + 1);
    printf("\n");
    for (int i = 0; i < n; i++) {
        if (!i)
            printf("x ");
        else
            printf("%d ", LCP[i]);
    }
    return 0;
}