[C++] 9248번 Suffix Array - 문자열, 접미사 배열과 lcp 배열

1. 문제

• 길이가 50만보다 작거나 같은 문자열이 주어졌을 때, Suffix Array와 LCP Array를 구하는 프로그램을 작성하시오.

<입력>

• -1-   알파벳 소문자로만 이루어진 문자열 S가 주어진다. S의 길이는 50만보다 작거나 같다.

<출력>

• -1-   Suffix Array
• -2-   LCP Array를 출력한다. LCP Array의 첫 값은 항상 'x'이다.

2. 재정의

• X

3. 해결방법

• 맨버-마이아스 알고리즘(Manber-Myers Algorithm), kasai 알고리즘을 이용한다.

4. 실수한 점, 개선할 점

• Manber-Myers Algorithm에서 정렬을 일반적인 sort로 구현하면 시간 복잡도가 \(O(nlgn^{2})\)이 되는데 이를 counting sort로 구현하면 \(O(nlgn)\)으로 줄일 수 있다. (이해하는 데 많이 힘들었어요...ㅜㅜ)

 

<코드>

#include <iostream>
#include <algorithm>
#include <string.h>

const int MAX_N = 500002;

using namespace std;

//문자열과 그 길이
char str[MAX_N];
int N;

//suffix array 알고리즘
//탐색할 위치
int t;
//그룹과 tmp 그룹, suffix array
int g[MAX_N], tg[MAX_N], SA[MAX_N];

//LCP 알고리즘
//i번째 문자열이 suffix array에 위치한 순서
int RANK[MAX_N];
//LCP 배열
int LCP[MAX_N];

bool cmp(int x, int y) {
    //배열의 크기를 넘어가는 것을 방지
    x = min(x, N), y = min(y, N);
    
    //그룹 번호가 같다면
    if(g[x] == g[y])
        return g[x+t] < g[y+t];
    
    //그룹 번호가 다르다면
    return g[x] < g[y];
}

void getSA() {
    t = 1;
    N = (int)strlen(str);
    
    //첫 글자 그룹을 정해주는 전처리
    for(int i=0; i<N; i++) {
        SA[i] = i;
        g[i] = str[i] - 'a';
    }
    
    //1, 2, 4, 8...씩 단어의 길이보다 작은 경우를 탐색
    //배열의 x+y>=n이면 -1을 넘겨줌으로써 항상 앞에 오도록 한다
    g[N] = -1;
    while(t <= N) {
        //그룹에 의한 정렬
        sort(SA, SA+N, cmp);
        
        //다음 그룹 배정
        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;
    }
}

void getLCP() {
    //RANK 배열에 i번째 문자열이 suffix array에 위치한 순서 대입
    for(int i=0; i<N; i++)
        RANK[SA[i]] = i;
    
    //탐색한 곳까지 같은 문자열 길이
    int match = 0;
    
    for(int i=0; i<N; i++) {
        int k = RANK[i];
        if(k) {
            //suffix array에서 인접한 문자열의 lcp를 구한다.
            int j = SA[k-1];
            
            while(str[j+match] == str[i+match])
                match++;
            
            LCP[k] = match;
            
            //제일 앞 한 문자를 빼준 두 문자열의 LCP는 match-1이다.
            if(match)
                match--;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> str;
    
    //suffix array 구하기
    getSA();
    //LCP 구하기
    getLCP();
    
    for(int i=0; i<N; i++)
        cout << SA[i]+1 << ' ';
    cout << '\n';
    
    cout << 'x' << ' ';
    for(int i=1; i<N; i++)
        cout << LCP[i] << ' ';
    
    return 0;
}

가면 갈수록 코드 길이가 늘어나고 있다. 무의식 중에 코드 길이가 점점 증가하고 있는 것이다.... 어떡하지..ㅎㅎ;;

 

 

<Suffix Array와 Manber-Myers Algorithm>

https://www.crocus.co.kr/613

접미사 배열(Suffix Array)

 

<LCP와 Kasai Algorithm - 1>

https://www.crocus.co.kr/614?category=209527 

LCP 알고리즘(Longest Common Prefix)

 

<LCP와 Kasai Algorithm - 2>

https://robustflame.tistory.com/entry/Suffix-Array-LCP-Array

Suffix Array, LCP Array

 

<Manber-Myers Algorithm을 Counting Sort로 구현하기>

https://cultivo-hy.github.io/suffix%20array/python/lcp/lcs/counting%20sort/2019/03/16/Suffix-Array-%EB%B0%8F-Counting-Sort-%EC%A0%95%EB%A6%AC/

[문자열] 접미사배열(Suffix Array)과 LCP(Longest Common Prefix), Counting Sort 정리

 

<pair<int, int> Counting Sort 하는 법>

https://plzrun.tistory.com/entry/Counting-Sort-Radix-Sort

Counting Sort & Radix Sort

 

<Suffix Array를 Counting Sort로 구현한 코드>

https://devbelly.tistory.com/38

[백준 9248] Suffix Array

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.