3789_Hidden password

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

suffix array nlog n으로 짠 코드

plzrun님 블로그에서 많이 참고하고 마리오블로그에서 lcp부분만 참고했다.

어떤 password가 주어졌을때

그걸 왼쪽으로 1번씩 민 각각의 문자열 중에 가장 사전순으로 작은 아이의 시작 인덱스를 출력하면 된다.

alabla 를 한번씩 민다면

lablaa

ablaal

blaala ... 이런식으로 총 n개가 나올 것이다

이것들을 사전 순으로 정렬했을때 가장 위에 오는 문자열의 맨 처음 문자가 원래 문자열의 몇번째 애인지 출력하는 거임.

결국에는 환형이 되므로 나는 입력받은 문자열을 붙여서 2배로 늘리고

가장 먼저 나오는 n보다 작은 인덱스를 출력하는데,

문자열이 사전 순으로 같은 경우 인덱스가 작은 걸 먼저 출력해야한다.

sa는 인덱스가 더 작은게 (더 기니까) 가장 늦게 나오고

만약 lcp[i] == n-sfx[i] 인 경우 현재 자신의 문자열 전체가 밑에 아이랑 중복된다는 것이므로 패스해준다.

#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100001
 
int T, n;
string s;
vector<int> g, ng, sfx, lcp, cnt, idx;
 
bool comp(int i, int j, int t) {
    if (g[i] == g[j]) return g[i + t] < g[j + t];
    return g[i] < g[j];
};
 
void getsfx() {
    int lim = max(n + 1, 257);
    g.clear(); ng.clear(); sfx.clear(); idx.clear();
    g.resize(n + 1), ng.resize(n + 1), sfx.resize(n), idx.resize(lim);
 
    for (int i = 0; i < n; ++i) {
        g[i] = s[i];
        sfx[i] = i;
    }
 
    if (n == 1) g[0] = 1;
 
    for (int t = 1; t < n; t <<= 1) {
        cnt.clear(); cnt.resize(lim + 1, 0);
        for (int i = 0; i < n; ++i) cnt[g[min(i + t, n)]]++;
        for (int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i) {
            idx[--cnt[g[min(i + t, n)]]] = i;
        }
 
        cnt.clear(); cnt.resize(lim + 1, 0);
        for (int i = 0; i < n; ++i) cnt[g[i]]++;
        for (int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i) {
            sfx[--cnt[g[idx[i]]]] = idx[i];
        }
 
        ng[sfx[0]] = 1;
        for (int i = 1; i < n; ++i) {
            if (comp(sfx[i - 1], sfx[i], t)) ng[sfx[i]] = ng[sfx[i - 1]] + 1;
            else ng[sfx[i]] = ng[sfx[i - 1]];
        }
 
        g = ng;
        if (ng[sfx[n - 1]] == n) break;
    }
 
    for (int i = 0; i < n; ++i) g[i]--;
    
}
 
void getlcp() {
    
    lcp.resize(n + 1);
    for (int i = 0, k = 0; i < n; ++i, k = max(k - 1, 0)) {
        if (g[i] == n-1) continue;
        for (int j = sfx[g[i] + 1]; s[i + k] == s[j + k]; ++k);
        lcp[g[i]] = k;
    }
 
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
    
    cin >> T;
    while (T--) {
        cin >> n;
        cin >> s;
        s += s;
        n += n;
 
        getsfx();
        getlcp();
 
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (sfx[i] < n / 2 && n-sfx[i] != lcp[i]) {
                res = sfx[i]; break;
            }
        }
 
        cout << res << '\n';
    }
}