백준 9248번 - Suffix Array

백준 9248번 - Suffix Array

www.acmicpc.net/problem/9248

9248번: Suffix Array

이 문제는 접미사 배열 문제이다.

오전에 맨버 마이어스 알고리즘을 공부해서 쉽게 풀 수 있을 것 같아서 풀어보았다.

테스트 케이스도 다 정확히 나오길래 드디어 플래 문제를 풀어보는구나 했는데 시간 초과..

 

도저히 어디가 문젠 지도 모르겠고.. 구글링은 귀찮고..

뭔가 이상해서 종만북 책을 다시 보니 더 읽을거리 부분에 뭔가가 써있네?

 

"두 접미사가 공유하는 최대 길이 접두사를 찾아야 하는 경우 직접 비교하는 commonPrefix보다 효율적으로 계산할 수 있는 알고리즘이 있습니다!"

 

하... 이걸 안 보고 헛짓거리를 하고 있었다.

 

구글에 Kasai LCP 치면 바로 나온다.

 

이 알고리즘은 가장 긴 접미사(원본 문자열)부터 길이가 짧아지는 순서대로 접미사를 탐색하며 최장 공통 접두사의 길이를 구한다. 이 알고리즘의 핵심적인 생각은 현재 탐색하고 있는 접미사의 최장공통접두사 길이가 k라면 다음에 탐색하는 접미사의 최장공통접두사의 길이는 k - 1 이상이라는 것이다. (feat. 위키백과)
이유는 길이가 짧아지는 순으로 계산하기 때문이다.

당연한 이야기지만 코드를 효율적으로 만들어 준다.

 

결국 짠 코드는 아래와 같다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
struct Comparator {
    const vector<int>& group;
    int t;
    Comparator(const vector<int>& _group, int _t) :group(_group), t(_t) {}
 
    bool operator()(int a, int b) {
        //첫 t글자가 다르면 이들을 이용해 비교한다.
        if (group[a] != group[b])return group[a] < group[b];
        //아니라면 S[a+t..]와 S[b+t..]의 첫 t글자를 비교한다.
        return group[a + t] < group[b + t];
    }
};
 
//s의 접미사 배열을 계산한다.
vector<int>getSuffixArray(const string& s) {
    int n = s.size();
    //group[i]는 첫 t글자를 기준으로 정렬 했을 때 S[i..]가 들어가는 그룹 번호
    //t=1일 때는 정렬할 것도 없이 S[i..]의 첫 글자로 그룹 번호를 정해 줘도 같은 효과가 있다.
    int t = 1;
    vector<int>group(n + 1);
    for (int i = 0; i < n; ++i) group[i] = s[i]; //처음에는 1글자만 비교하므로 상관없음
    group[n] = -1; //길이가 0인 접미사를 예외처리
    //결과적으로 접미사 배열이 될 반환 값. 이 배열을 lg(n)번 정렬한다.
    vector<int>perm(n);
    for (int i = 0; i < n; ++i) perm[i] = i;
    while (t < n) {
        //group[]은 첫 t글자를 기준으로 계산해 두었다.
        //첫 2t글자를 기준으로 perm을 다시 정렬한다.
        Comparator compareUsing2T(group, t); //perm을 그룹을 기준으로 정렬하기 위함
        sort(perm.begin(), perm.end(), compareUsing2T); //여기서 어차피 정렬 함. 
        t *= 2;
        if (t >= n)break; //2t 글자가 n을 넘는다면 이제 접미사 배열 완성
        //2t글자를 기준으로 한 새로운 그룹 정보를 만든다.
        vector<int>newGroup(n + 1);
        newGroup[n] = -1;
        newGroup[perm[0]] = 0;
        //내가 이해한 이 아래의 코드는 perm에서 다른그룹이라면(2t글자가 같지 않았다면)
        //그룹 번호를 +1 해줌으로써 그룹 번호 갱신하는 코드임
        for (int i = 1; i < n; ++i) {
            if (compareUsing2T(perm[i - 1], perm[i])) {
                newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
            }
            else
                newGroup[perm[i]] = newGroup[perm[i - 1]];
        }
        group = newGroup;
    }
    return perm;
}
 
int commonPrefix(const string& s, int i, int j) {
    //생각보다 단순하게 구한다. 같으면 증가시키면 끝
    int k = 0;
    while (i < s.size() && j < s.size() && s[i] == s[j]) {
        ++i; ++j; ++k;
    }
    return k;
}
 
vector<int> kasai(string& txt, vector<int>& suffixArr)
{   // kasai 알고리즘
    //가장 긴 접미사(원본 문자열)부터 길이가 짧아지는 순서대로 접미사를 탐색하며 최장공통접두사의 길이를 구한다. 
    //이 알고리즘의 핵심적인 생각은 현재 탐색하고 있는 접미사의 최장공통접두사 길이가 k라면 
    //다음에 탐색하는 접미사의 최장공통접두사의 길이는 k - 1 이상이라는 것이다.
    //이유는 길이가 짧아지는 순으로 계산하기 때문
    int n = suffixArr.size();
    vector<int> lcp(n, 0);
    vector<int> invSuff(n, 0);
    //접미사 배열을 길이가 짧은 순으로 새로 저장한다.
    for (int i = 0; i < n; i++)
        invSuff[suffixArr[i]] = i;
    int k = 0;
    for (int i = 0; i < n; i++)
    {
        if (invSuff[i] == n - 1) //만약 가장 긴 부분 문자열(본 문자열)이라면 공통 접두사 존재 불가
        {
            k = 0;
            continue;
        }
        //j에는 비교할 다음 문자열을 저장. 즉 접미사 배열의 다음 문자열
        int j = suffixArr[invSuff[i] + 1];
 
        // k 번째 index에서 일치 시작
        // 최소 k-1개가 일치
        while (i + k < n && j + k < n && txt[i + k] == txt[j + k])
            k++;
 
        lcp[invSuff[i]] = k; // lcp 배열 갱신
 
        // 다음 탐색때는 최대 k-1까지만 가능하므로 k-- 실행
        if (k > 0)
            k--;
    }
 
    return lcp;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string str;
    cin >> str;
    vector<int>suffixArray = getSuffixArray(str);
    vector<int>LCPArray = kasai(str, suffixArray);
    for (int i = 0; i < suffixArray.size(); i++) {
        cout << suffixArray[i] + 1 << " ";
    }
    cout << "\n" << "x ";
    for (int i = 0; i < LCPArray.size() - 1; i++) {
        cout << LCPArray[i] << " ";
    }
    cout << "\n";
}

솔직히 내가 풀었다기 보단 종만북과 구글이 합작했지만..

나중을 위해 기록해 놓는다.