백준 9248번: Suffix Array

문제링크

https://www.acmicpc.net/problem/9248

9248번: Suffix Array

풀이

• SA 구하기
  • suffix 들을 앞부분 길이 1, 2, 4, 8 ... 에 대해서 정렬
  • 앞부분 길이 d 에서 정렬한 정보를 2 * d 를 정렬할 때 이용할 수 있음
• LCP 구하기 (Kasai's algorithm)
  • 인덱스 0 시작, 1시작, ... 접미사들에 대해서 차례로 lcp 를 구한다
  • $lcp[isa[i]] = k$ 이면 $lcp[isa[i + 1]] \geq k - 1$ 임을 이용한다

코드

• 시간복잡도
  • 문자열길이: $N$ 
  • SA: $O(Nlog^2N)$
    • counting sort 로 정렬시 $O(NlogN)$
  • LCP: $O(O(SA) + N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string s;
    cin >> s;

    auto buildSA = [&](string& s) {
        int N = s.size();
        vector<int> sa(N), r(2 * N, 0), nr(2 * N);
        for (int i = 0; i < N; ++i) {
            sa[i] = i;
            r[i] = s[i];
        }

        for (int d = 1; d < N; d <<= 1) {
            auto cmp = [&](int i, int j) {
                return r[i] < r[j] || (r[i] == r[j] && r[i + d] < r[j + d]);
            };
            sort(all(sa), cmp);
            nr[sa[0]] = 1;
            for (int i = 1; i < N; ++i) {
                nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
            }
            r = nr;
        }
        for (auto& e: sa) {
            cout << e + 1 << ' ';
        }
        cout << '\n';
        return sa;
    };

    auto buildLCP = [&](string& s) {
        int N = s.size();
        auto sa = buildSA(s);
        vector<int> isa(N), lcp(N);
        for (int i = 0; i < N; ++i) {
            isa[sa[i]] = i;
        }

        for (int k = 0, i = 0; i < N; ++i) {
            if (isa[i] == 0) continue;
            for (int j = sa[isa[i] - 1]; max(i, j) + k < N && s[i + k] == s[j + k]; ++k);
            lcp[isa[i]] = k ? k-- : 0;

        }
        return lcp;
    };

    auto lcp = buildLCP(s);

    for (int i = 0; i < lcp.size(); ++i) {
        if (i) {
            cout << lcp[i] << ' ';
        } else {
            cout << "x ";
        }
    }
}