여러 문자열을 허용하는 Suffix Array class

이론적인 내용은 나보다는 여기나 여기같은 다른 사람들 블로그에 정리가 잘 되있다.

 

그냥 나중에 내가 코딩할 때 편하려고 코드 쟁여놓는 것이 글 쓰는 목적이라서 정리는 대충한다.....

 

 

 

기본적으로 Suffix Array는 문자열을 길이 1, 2, 4, 8, 16... 만큼 봐서

해당 길이에 대응되는 문자열끼리 정렬을 수행하는 방식이다.

이 때 2^k 문자열을 비교할 때 2^(k-1)번째 정렬된 결과를 바탕으로 정렬을 수행한다.

 

대충 pair[k][i] = pair<int, int>(pa[k-1][i] , pa[k-1][i + 2^(k-1)]) 순서쌍을 만든 다음

이 순서쌍을 기준으로 정렬해서

최종적으로 pa[k][i] = {pair[k][i]의 순위} 가 된다..

 

여기서 i+2^(k-1)이 기존 문자열을 넘어가버리면

사전순으로 가장 앞쪽에 있는 가상의 문자를 만들어서 그 친구를 집어넣어서 해결한다.

 

이 때 집어넣는 '가상의 문자'를 넣는 과정을 약간 개조하면

여러개의 문자열에 대한 Suffix Array를 만들 수 있게 된다.

 

대충 이렇게 말이다.

 

이렇게 만든 Suffix Array를 통해서 LCP(Least Common Prefix) 값을 구하면

BOJ 9249번 문제를 해결할 수 있다.

 

 

아래 코드는 내가 만든 Suffix Array 클래스랑

이를 이용해서 문제를 해결한 코드이다.

 

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
class SuffixArray {
public:
    const static int MAX_STRING = 200009;
    const static int MAX_LEN = 200009;
    const static int LOG_LEN = 20;
    const static int INF = 1000000009;
    int pa[LOG_LEN][MAX_LEN];
    int len_sum[MAX_STRING + 1];
    int n;
    int m;
    SuffixArray() {
        inil();
    }
    void inil() {
        n = 0;
    }
    void add(int* a, int al) {
        for (int i = 0; i < al; ++i)
            pa[0][i + len_sum[n]] = a[i];
        len_sum[n + 1] = len_sum[n] + al;
        n++;
    }
    void add(char* a, int al) {
        for (int i = 0; i < al; ++i)
            pa[0][i + len_sum[n]] = a[i];
        len_sum[n + 1] = len_sum[n] + al;
        n++;
    }
    int next[MAX_LEN];
    int ccnt[MAX_LEN + MAX_STRING + 1];
    int ord[MAX_LEN];
    int ord2[MAX_LEN];
    void sort_c(int si, int ei) {
        if (ei - si <= 1)return;
        int i, j, k;
        int mi = (si + ei) / 2;
        sort_c(si, mi);
        sort_c(mi, ei);
        for (i = k = si, j = mi; i < mi && j < ei; ++k) {
            if (ccnt[i] < ccnt[j])ord[k] = ccnt[i++];
            else ord[k] = ccnt[j++];
        }
        for (; i < mi; ++k)ord[k] = ccnt[i++];
        for (; j < ei; ++k)ord[k] = ccnt[j++];
        for (i = si; i < ei; ++i)
            ccnt[i] = ord[i];
    }
    int find_c(int si, int ei, int key) {
        int l, r, mid;
        l = si; r = ei;
        while (l < r) {
            mid = (l + r) / 2;
            if (ccnt[mid] == key)return mid;
            if (ccnt[mid] < key)l = mid + 1;
            else r = mid;
        }
        return l;
    }
    void pre_build() {
        int i, j, k;
        for (i = 0; i < len_sum[n]; ++i)
            ccnt[i] = pa[0][i];
        k = len_sum[n];
        sort_c(0, k);
        for (i = j = 0; i < k; ++i) {
            if (ccnt[i] != ccnt[j]) {
                ++j;
                ccnt[j] = ccnt[i];
            }
        }
        k = j + 1;
        for (i = 0; i < len_sum[n]; ++i) {
            pa[0][i] = find_c(0, k, pa[0][i]);
        }
 
    }
    void build() // O(n (log n) )
    {
        pre_build();
        int i, j, k;
        int len;
        len = 1;
        m = 0;
        for (j = 0; j < LOG_LEN - 1; ++j) {
            //make pa[j+1][i] by pa[j][i]
            //sort by pair(pa[j][i], pa[j][i+len]). len = 2^j
            //pa[j+1][i] is rank of pair.
            int rank = 0;
            for (i = 0; i <= n + len_sum[n]; ++i) {
                ccnt[i] = 0;
            }
            for (i = 0; i < n; ++i) {
                for (k = len_sum[i]; k < len_sum[i + 1]; k++)
                {
                    if (k + len < len_sum[i + 1])
                    {
                        next[k] = pa[j][k + len] + n;
                    }
                    else
                    {
                        next[k] = i;
                    }
                    ++ccnt[next[k]];
                }
            }
            for (i = 0; i < n + len_sum[n]; ++i) {
                ccnt[i + 1] += ccnt[i];
            }
            for (i = n - 1; i >= 0; --i) {
                for (k = len_sum[i + 1] - 1; k >= len_sum[i]; --k)
                {
                    ord[--ccnt[next[k]]] = k;
                }
            }
            for (i = 0; i < len_sum[n]; ++i) {
                ccnt[i] = 0;
            }
            for (i = 0; i < len_sum[n]; ++i) {
                ++ccnt[pa[j][i]];
            }
            for (i = 0; i < len_sum[n] - 1; ++i) {
                ccnt[i + 1] += ccnt[i];
            }
            for (i = len_sum[n] - 1; i >= 0; --i) {
                ord2[--ccnt[pa[j][ord[i]]]] = ord[i];
            }
            rank = 0;
            for (i = 0; i < len_sum[n];i++) {
                pa[j + 1][ord2[i]] = rank;
                if (i + 1 < len_sum[n] && pa[j][ord2[i]] == pa[j][ord2[i + 1]] && next[ord2[i]] == next[ord2[i + 1]])
                    continue;
                ++rank;
            }
 
            m = j + 1;
 
            if (rank == len_sum[n]) break;
            len *= 2;
        }
    }
    int get_length(int pi, int _pl, int qi, int _ql) {
        // return longest common string length with
        // a[pi][pl] ^ a[qi][ql].
        // pi is string number. pl is position of suffix string.
        if (pi == qi && _pl == _ql) {
            return len_sum[pi + 1] - len_sum[pi] - _pl;
        }
        int res = 0;
        int i, j, k;
        int len;
        int pl = len_sum[pi] + _pl;
        int ql = len_sum[qi] + _ql;
        len = 1 << (m - 1);
        for (j = m - 1; j >= 0; --j) {
            if (pa[j][pl] == pa[j][ql]) {
                res += len;
                pl += len;
                ql += len;
            }
            len /= 2;
        }
        if (res > len_sum[pi + 1] - len_sum[pi] - _pl)
            res = len_sum[pi + 1] - len_sum[pi] - _pl;
        if (res > len_sum[qi + 1] - len_sum[qi] - _ql)
            res = len_sum[qi + 1] - len_sum[qi] - _ql;
        return res;
    }
 
    int* suffix_array() {
        return pa[m];
    }
    int get_rank(int pi, int pl) {
        return pa[m][len_sum[pi] + pl];
    }
};
 
int n;
char a[200009];
int m;
char b[200009];
SuffixArray sf;
int rv[200009];
int main() {
    int i, j, k, l;
    scanf("%s", a);
    for (n = 0; a[n]; n++);
    scanf("%s", b);
    for (m = 0; b[m]; m++);
    sf.inil();
    sf.add(a, n);
    sf.add(b, m);
    sf.build();
    int* r = sf.suffix_array();
    for (i = 0; i < n+m; i++) {
        rv[r[i]] = i;
    }
    
    int res=0;
    int ri=0;
    for (i = 1; i < n+m; i++) {
        int pi = rv[i - 1];
        int qi = rv[i];
        if ((pi < n) ^ (qi < n))
        {
            int len;
            if (pi < n)len = sf.get_length(0, pi, 1, qi - n);
            else len = sf.get_length(1, pi - n, 0, qi);
            if (res < len) {
                res = len;
                ri = pi < n ? pi : qi;
            }
        }
    }
    printf("%d\n", res);
    a[ri + res] = 0;
    printf("%s\n", a + ri);
}

 

내가 짠 코드이니만큼 코드가 난잡하고 정리가 안되있지만

어쩔 수 없지..난 이런 사람인걸..ㅠㅠ

 

MAX_STRING개의 문자열을 넣을 수 있고

모든 문자열의 길이 합이 MAX_LEN을 넘지 않으면 된다.

LOG_LEN은 MAX_LEN의 로그값인데.. 나같은 경우는 한 2정도 더해서 사용하는 편이다.

 

내부적으로 쓰는 pre_build() 에서 O(N log N);

그 이후 Suffix Array를 생성하는 build는 O(N log N). 내부적으로 Suffix Array가 완성되면(==더이상 갱신될게 없으면) 컷팅이 되긴 한다.

이 이후 두 개의 suffix string이 주어졌을 때 LCP의 길이를 구하는 과정은 O(log N)만큼의 시간이 소요된다.

 

Suffix_Array.cpp

0.00MB

color scripter 처음 써봐서 혹시 몰라서 코드 파일도 첨부.

 

추천하는 연습문제 (난이도순)

BOJ 2020 부분 염기서열 (2020년 들어서 가장 먼저 푼 2020번 문제)

BOJ 13576 Prefix와 Suffix

BOJ 13276 Prefix와 Suffix 놀랍게도 위의 문제랑 다른 문제이다.

BOJ 13506 카멜레온 문자열

사실 난이도는 다 고만고만하다. 그냥 직접 짠 Suffix Array 라이브러라 테스트한다는 느낌으로 풀면 된다.

(Suffix Array로 할 수 있는 application들이 뭐가 있을까를 직접 경험할 수도 있다.)

 

-- 2020.01.01 14:23 추가 --

BOJ 9236 고급 레스토랑 고만고만하지 않은 문제 추가.

5년전에 푼 문제긴 한데.. 어떻게 풀어야할지 지금도 잘 모르겠음ㅋㅋ