Suffix Array & LCP (C++11 Code Only)

여기엔 코드만 올린다.

설명은 바로 이전 글 2개에 걸쳐서 설명이 되어있다.

내가 acm reference로 썼던 나름 깔끔한 코드다.

지금 코드는 어떨지 모르겠는데 koosaga님 블로그를 통해 배웠기 때문에 상당부분 koosaga님 코드와 비슷할 거라 생각한다.

그래서 출처는 koosaga님 블로그로 밝힌다. (http://koosaga.myungwoo.kr/entry/Suffix-Array-접미사-배열)

다만, 코드는 내가 직접 작성하긴 했다.

Suffix Array: → 설명이 있는 내가 올린 포스팅: http://plzrun.tistory.com/entry/Suffix-Array-ONlogNlgN과-ONlogN-구현-및-설명 (2017.06.11 수정)

LCP: → 약간 설명이 있는 내가 올린 포스팅: http://plzrun.tistory.com/entry/문자열-처리-알고리즘-LCP

해당 코드의 전체 시간 복잡도:

//Suffix Array: O(NlogN), LCP: O(N)    made by plzrun.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#define CHARNUM 256
using namespace std;
vector<int> sfx,g,ng,cnt,orderToIdx;
vector<int> lcp, prevsfx, plcp;
////get Suffix Array O(NlogN) using counting sort.
vector<int> getsfx(const string &s) {
    const int n = s.size();
    int lim = max(n+1, CHARNUM+1);
    sfx.clear(); g.clear(); ng.clear(); orderToIdx.clear();
    sfx.resize(n), g.resize(n+1), ng.resize(n+1), orderToIdx.resize(n+1,0);
 
    for(int i=0; i<n; i++) sfx[i]=i, g[i]=s[i];
 
    for(int t=1; t<n; t<<=1) {
        cnt.clear(); cnt.resize(lim,0);
        for(int i=0; i<n; i++) cnt[g[min(i+t,n)]]++;
        for(int i=1; i<lim; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) orderToIdx[--cnt[g[min(i+t,n)]]]=i;
 
        cnt.clear(); cnt.resize(lim,0);
        for(int i=0; i<n; i++) cnt[g[i]]++;
        for(int i=1; i<lim; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) sfx[--cnt[g[orderToIdx[i]]]]=orderToIdx[i];
 
        auto cmp = [&](int i, int j)->bool{
            if(g[i]==g[j]) return g[i+t]<g[j+t];
            else return g[i]<g[j];
        };
 
        ng[sfx[0]]=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;
    }
 
    //get LCP O(N)
    lcp.clear(); prevsfx.clear(); plcp.clear();
    lcp.resize(n); prevsfx.resize(n+1); plcp.resize(n+1);
 
    prevsfx[sfx[0]]=-1;
    for(int i=1; i<n; i++) prevsfx[sfx[i]]=sfx[i-1];
    for(int i=0, common=0; i<n; i++) {
        if(prevsfx[i]==-1) plcp[i]=0;
        else {
            while(s[i+common] == s[prevsfx[i] + common]) common++;
            plcp[i]=common;
            common = max(common-1,0);
        }
    }
    for(int i=0; i<n; i++) lcp[i]=plcp[sfx[i]];
 
    return sfx;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;
    vector<int> sfx = getsfx(s);
 
    printf("sfx: ");
    for(auto &p : sfx) printf("%d ", p);
    puts("");
 
    printf("lcp: ");
    for(auto &p : lcp) printf("%d ", p);
    puts("");
 
    return 0;
}