[백준] 13264 접미사 배열2

suffix array를 이용하는 문제다

suffix array에 관한건 구글링을....!

원리는 1,2,4,8...,len 까지 이전에 구한것을 이용해 O(1)만에 계속 구해가는 것이다

suffix array에 대한 설명이 없는점 죄송 ㅎㅎ 어렵네요 이거..

저도 아직 완벽하게 정리가 안된지라 ㅎㅎ

좀 더 공부해서 나중에 이론게시판에 쓰는걸로..!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
    string s; cin >> s;
    int n = s.size(), l = 1;
    vector<int> sa(n), g(n + 1), ng(n + 1);
    g[n] = ng[n] = -1;
    for (int i = 0; i < n; i++) sa[i] = i;
    for (int i = 0; i < n; i++) g[i] = s[i];
    auto cmp = [&](int u, int v) {
        if (g[u] == g[v]) return g[u+l] < g[v+l];
        return g[u] < g[v];
    };
    while (l < n) {
        sort(sa.begin(), sa.end(), cmp);
        ng[sa[0]] = 0;
        for (int i = 0; i < n - 1; i++) ng[sa[i + 1]] = ng[sa[i]] + cmp(sa[i], sa[i + 1]);
        g = ng;
        l <<= 1;
    }
    for (int i = 0; i < n; i++) printf("%d\n", sa[i]);
}