Suffix Array & LCP 알고리즘

반응형

<Suffix Array & LCP 알고리즘>

 

Suffix Array에 접미사들을 저장하고, Counting Sort로 정렬해주었다.

 

# Counting Sort는 O(N)시간 복잡도를 가지며, 주로 문자열을 다룰 때 (26개의 알파벳) 주로 사용된다.

Quick Sort가 O(NlogN) 복잡도를 가지는 것에 비해서는 매우 짧지만, 같은 패턴이 나오는 문자의 길이가 길어질 수록 Counting Sort도 비효율적이다.

 

Suffix Array를 구성하고 이를 활용해 LCP를 구성한다.

# LCP (Longest Common Prefix) : 접미사 배열에서 i번째 접미사와 i-1번째 접미사 사잉서 일치하는 접두사의 길이

LCP 알고리즘을 사용하는 이유는 이전에 비교했던 결과를 최대한 이용해서 i번째 접미사를 비교할 때, i-1번째 접미사에서 비교한 다음부터 비교하면 되기 때문에 효율적이다.

시간복잡도는 O(N)이다.

 

다음은 문자열이 들어왔을 때 Suffix Array와 LCP를 구해 각각 출력하는 코드이다.

#백준 3033번: 가장 긴 문자열

 

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
 
int lcp[500000];
string str;
vector<int> sfx, g, ng;    //suffix array, group number, new group number
//sfx : suffix들을 정렬했을 때, x번째 suffix의 index
//g :  S[x:-1]의 그룹번호
//ng : suffix들을 정렬했을 때, x번째 suffix의 그룹번호
 
vector<int> getsfx(string &str) {
    int n = str.size();
    sfx.resize(n);
    g.resize(n + 1);
    ng.resize(n + 1);
    for (int i = 0; i < n; i++) {
        sfx[i] = i;
        g[i] = str[i];
    }
    g[n] = 1;
    for (int t = 1; t < n; t <<= 1) {
        auto cmp = [&](int i, int j) {
            if (g[i] == g[j])
                return g[i + t] < g[j + t];
            else
                return g[i] < g[j];
        };
        sort(sfx.begin(), sfx.end(), cmp);    //sfx를 g를기준으로 정렬
        ng[sfx[0]] = 0;
        ng[n] = -1;
        for (int i = 1; i < n; i++) {
            if (cmp(sfx[i - 1], sfx[i]))
                ng[sfx[i]] = ng[sfx[i - 1]] + 1;
            else
                ng[sfx[i]] = ng[sfx[i - 1]];
        }
        g = ng;
    }
    return sfx;
}
int maxx(int a, int b) {
    return a > b ? a : b;
}
int main() {
    freopen("sample_input.txt","r",stdin);
    int T, N;
    register int t, i, j, k;
    
    getline(cin, str);
    vector<int> sfx = getsfx(str);
    for (i = 0; i < sfx.size(); i++) {
        printf("%d ", sfx[i]+1);
    }
    printf("\n");
    int n = sfx.size();
    for (i = 0, k = 0; i < n; i++, k=maxx(k-1, 0)) {
        if (g[i] == n-1)
            continue;
        for (j = sfx[g[i] + 1]; str[i + k] == str[j + k]; k++);
        lcp[g[i]] = k;
    }
    printf("x ");
    for (i = 0; i < n-1; i++) {
        printf("%d ", lcp[i]);
    }
    printf("\n");
    return 0;
}