Suffix Array

#include <bits/stdc++.h>

#define MAX_N 500002
#define ll long long
#define vll vector<ll>
#define all(a) begin(a), end(a)
using namespace std;

string s;

vll SA() {
    ll n = s.length(), t = 1;
    vll sa(n), tg(n + 1), g(n + 1);
    for(ll i = 0; i < n; i++) {
        sa[i] = i;
        g[i] = s[i] - 'a';
    }

    while(t <= n) {
        g[n] = -1;
        auto cmp = [&](ll x, ll y) {
            if(g[x] == g[y])
                return g[x+t] < g[y+t];
            return g[x] < g[y];
        };

        sort(all(sa), cmp);

        tg[sa[0]] = 0;
        for(ll i = 1; i < n; i++)
            tg[sa[i]] = tg[sa[i-1]] + cmp(sa[i-1], sa[i]);

        g = tg;
        t<<=1;
    }
    return sa;
}

vll LCP(vll& sa) {
    ll n = s.length(), len = 0;
    vll rsa(n), lcp(n);
    for(ll i = 0; i < n; i++) {
        rsa[sa[i]] = i;
    }
    for(ll i = 0; i < n; i++) {
        ll k = rsa[i];
        if(k) {
            ll j = sa[k-1];
            while(s[i + len] == s[j + len]) ++len;
            lcp[k] = len;
            if(len) --len;
        }
    }
    return lcp;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>s;
    auto sa = SA();
    auto lcp = LCP(sa);

    ll n = s.length();
    for(ll i = 0; i < n; i++) cout<<(sa[i] + 1)<<' ';cout<<"\nx ";
    for(ll i = 1; i < n; i++) cout<<lcp[i]<<' ';cout<<"\n";

    return 0;
}