Suffix Array

Suffix Array

suffix array란 string의 suffix로 이루어진 sorted array 이다.

예시를 통해 이해하도록 하자.

"camel" 이란 string이 suffix는 다음과 같다.

Index	suffix string
0	camel
1	amel
2	mel
3	el
4	l

이것을 순서대로 정렬하면,

Index	suffix string
1	amel
0	camel
3	el
4	l
2	mel

따라서 suffix array는 {1,0,3,4,2} 가 된다.

suffix string을 저장할 필요 없이 index만 저장하면 된다.

Code

---

1. naive하게 만들기

 typedef struct Suffix{
        string s;
        int idx;
    }Suffix;

bool Compare(Suffix a, Suffix b){
        return a.s < b.s;
}

int* naive_suffix_array(string s){
    int n = s.size();
    Suffix* A = (Suffix*)malloc(sizeof(Suffix)*n);
    int* T = (int*)malloc(sizeof(int)*n);

    for(int i = 0 ; i < s.size();i++){
        A[i].s = s.substr(i,n-i);
        A[i].idx = i;
    }

    sort(A,A+n,Compare);

    for(int i = 0; i < n; i++)
        T[i] = A[i].idx;

    return T;
}

이 경우 sorting할 때 $O(n^{2}*log(n))$ 이 걸린다.

Compare를 할 때 O(1)이 아니라 O(n) 이 걸리기 때문이다!

T[n] = 2*T[n/2] + O(n^2) 에서

(트리를 그려보면 높이는 log n이고 각 높이에서 n^2 만큼 계산하므로.. 그림 잘 생각해두자.)

적용할 수 있는 문제

---

차차 업데이트 해야겠다. -_- string에서의 정렬과 관련된 문제에 적용할 수 있을 것이다.