글 읽기 - suffix array 코드 중 질문드립니다

devbelly 3년 전 0

블로그에서 코드를 보다가 이해가 가지 않는 부분 및 확인받고싶은 부분이 있어서 질문드립니다.

[코드 출처]

https://plzrun.tistory.com/entry/Suffix-Array-ONlogNlgN%EA%B3%BC-ONlogN-%EA%B5%AC%ED%98%84-%EB%B0%8F-%EC%84%A4%EB%AA%85

**사전지식**

vector<int> g : g[i] 는 원래의 문자열 i 인덱스의 순위를 나타냅니다.

vector<int> ng : 다음 g를 갱신하기 위한 ng

vector<int> cnt : 기수정렬용 cnt

**질문 목록**

1. 10번째줄 lim은 기수정렬때 cnt 배열의 크기를 사용하기 위함으로 이해했습니다.

257의 의미는 모든 char형을 담겠다는 표현같은데 왜 n+1이랑 max를 취하나요?

2 . orderToidx 배열은 기수정렬을 1차적으로 한 idx를 나타내는데, 배열의 크기를 n+1까지 해야하나요? n까지면 오류가 발생하나요?

3. 30번째줄 ng[sfx[0]]=1 에서 1은 g[n]. 즉 빈 문자열을 최우선순위(0)로 두기위해서 1로 적은것이 맞나요?

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
vector<int> g,ng,sfx,cnt,orderToIdx;
vector<int> getsfx(string &s) {
    int n=s.size();
    int lim = max(257,n+1);
    g.resize(n+1); ng.resize(n+1); sfx.resize(n); orderToIdx.resize(n+1);
    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 idx=n-1; idx>=0; idx--) orderToIdx[--cnt[g[min(idx+t,n)]]]=idx;
        //orderToIdx[x]=idx; => pair에서 second기준으로 정렬했을 때, second기준으로 x번째에 해당하는 index는 idx라는 뜻이다.
 
        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];
        //sfx[x]=idx; => pair에서 second기준으로 정렬후 first기준으로 다시 stable sort를 했을 때, 순서로 x번째에 해당하는 인덱스는 idx라는 뜻이다.
 
        auto cmp = [&](int i, int j) {
            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;
    }
    return sfx;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;
    vector<int> sfx = getsfx(s);
    for(int i=0; i<sfx.size(); i++) {
        printf("%d ", sfx[i]);
    }
    return 0;
}


출처: https://plzrun.tistory.com/entry/Suffix-Array-ONlogNlgN과-ONlogN-구현-및-설명 [plzrun's algorithm]

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

suffix array 코드 중 질문드립니다

devbelly 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말