代码

#pragma GCC optimize("O3")
#include <cstdio>
#include <cstring>

static const int MAXN = 100010;

static unsigned char S[MAXN];
static int SA[MAXN];
static int RANK[MAXN];
static int H[MAXN];

static unsigned char POOL[1 << 24];
static size_t pp = 0;
static inline void *BALLOC(size_t sz) {
    sz = (sz + 15) & ~(size_t)15;
    void *r = POOL + pp;
    pp += sz;
    return r;
}

template <class T>
static void induce(T *__restrict__ s, unsigned char *__restrict__ t, int *__restrict__ sa, int n, int K,
                   int *__restrict__ SL, int *__restrict__ SS, int *__restrict__ BUF, const int *__restrict__ lms, int m) {
    memset(sa, -1, n * 4);
    memcpy(BUF, SS, (K + 1) * 4);
    for (int i = 0; i < m; i++) {
        int d = lms[i];
        sa[BUF[s[d]]++] = d;
    }
    memcpy(BUF, SL, (K + 1) * 4);
    sa[BUF[s[n - 1]]++] = n - 1;
    for (int i = 0; i < n; i++) {
        int v = sa[i];
        if (v >= 1 && !t[v - 1]) sa[BUF[s[v - 1]]++] = v - 1;
    }
    memcpy(BUF, SL, (K + 1) * 4);
    for (int i = n - 1; i >= 0; i--) {
        int v = sa[i];
        if (v >= 1 && t[v - 1]) sa[--BUF[s[v - 1] + 1]] = v - 1;
    }
}

template <class T>
static void sais(T *__restrict__ s, int *__restrict__ sa, int n, int K) {
    if (n == 1) { sa[0] = 0; return; }
    if (n == 2) {
        if (s[0] < s[1]) { sa[0] = 0; sa[1] = 1; }
        else { sa[0] = 1; sa[1] = 0; }
        return;
    }
    unsigned char *t = (unsigned char*)BALLOC(n);
    t[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--) {
        t[i] = (s[i] == s[i + 1]) ? t[i + 1] : (s[i] < s[i + 1]);
    }

    int *SL = (int*)BALLOC((K + 1) * 4);
    int *SS = (int*)BALLOC((K + 1) * 4);
    int *BUF = (int*)BALLOC((K + 1) * 4);
    memset(SL, 0, (K + 1) * 4);
    memset(SS, 0, (K + 1) * 4);
    for (int i = 0; i < n; i++) {
        if (!t[i]) SS[s[i]]++;
        else SL[s[i] + 1]++;
    }
    for (int i = 0; i < K; i++) {
        SS[i] += SL[i];
        SL[i + 1] += SS[i];
    }

    int *LMSMAP = (int*)BALLOC((n + 1) * 4);
    memset(LMSMAP, -1, (n + 1) * 4);
    int *LMS = (int*)BALLOC(n * 4);
    int m = 0;
    for (int i = 1; i < n; i++) {
        if (!t[i - 1] && t[i]) { LMSMAP[i] = m; LMS[m] = i; m++; }
    }

    induce(s, t, sa, n, K, SL, SS, BUF, LMS, m);

    if (m) {
        int *SLMS = (int*)BALLOC(m * 4);
        {
            int p = 0;
            for (int i = 0; i < n; i++) {
                int v = sa[i];
                if (v >= 0 && LMSMAP[v] != -1) SLMS[p++] = v;
            }
        }
        int *RS = (int*)BALLOC(m * 4);
        int rec_upper = 0;
        RS[LMSMAP[SLMS[0]]] = 0;
        for (int i = 1; i < m; i++) {
            int l = SLMS[i - 1], r = SLMS[i];
            int end_l = (LMSMAP[l] + 1 < m) ? LMS[LMSMAP[l] + 1] : n;
            int end_r = (LMSMAP[r] + 1 < m) ? LMS[LMSMAP[r] + 1] : n;
            bool same = true;
            if (end_l - l != end_r - r) {
                same = false;
            } else {
                while (l < end_l) {
                    if (s[l] != s[r]) break;
                    l++; r++;
                }
                if (l == n || s[l] != s[r]) same = false;
            }
            if (!same) rec_upper++;
            RS[LMSMAP[SLMS[i]]] = rec_upper;
        }
        int *RSA = (int*)BALLOC(m * 4);
        sais(RS, RSA, m, rec_upper + 1);
        for (int i = 0; i < m; i++) SLMS[i] = LMS[RSA[i]];
        induce(s, t, sa, n, K, SL, SS, BUF, SLMS, m);
    }


}

static const char D2[] =
"00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";

static unsigned int D4[10000];
static void initD4() {
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            D4[i * 100 + j] = (unsigned int)(unsigned char)D2[i * 2]
                | ((unsigned int)(unsigned char)D2[i * 2 + 1] << 8)
                | ((unsigned int)(unsigned char)D2[j * 2] << 16)
                | ((unsigned int)(unsigned char)D2[j * 2 + 1] << 24);
        }
    }
}

static char inbuf[1 << 20];
static char outbuf[1 << 22];

static inline char* wint(char *p, int v, char sep) {
    if (v >= 100000) {
        *p++ = '1'; *p++ = '0'; *p++ = '0'; *p++ = '0'; *p++ = '0'; *p++ = '0';
        *p++ = sep; return p;
    }
    if (v >= 10000) {
        int q = v / 10000;
        *p++ = '0' + q;
        unsigned int w = D4[v - q * 10000];
        *(unsigned int*)p = w; p += 4;
        *p++ = sep; return p;
    }
    if (v >= 1000) {
        unsigned int w = D4[v];
        *(unsigned int*)p = w; p += 4;
        *p++ = sep; return p;
    }
    if (v >= 100) {
        int q = v / 100;
        *p++ = '0' + q;
        v -= q * 100;
        p[0] = D2[v * 2]; p[1] = D2[v * 2 + 1];
        p += 2;
        *p++ = sep; return p;
    }
    if (v >= 10) {
        p[0] = D2[v * 2]; p[1] = D2[v * 2 + 1];
        p += 2;
        *p++ = sep; return p;
    }
    *p++ = '0' + v;
    *p++ = sep; return p;
}

int main() {
    initD4();
    size_t nread = fread(inbuf, 1, sizeof(inbuf), stdin);
    int n = 0;
    while (n < (int)nread && inbuf[n] >= 'a' && inbuf[n] <= 'z') {
        S[n] = (unsigned char)(inbuf[n] - 'a');
        n++;
    }

    pp = 0;
    sais<unsigned char>(S, SA, n, 26);

    for (int i = 0; i < n; i++) RANK[SA[i]] = i;

    S[n] = 255;
    int k = 0;
    for (int i = 0; i < n; i++) {
        int r = RANK[i];
        if (r == 0) { k = 0; continue; }
        if (k) k--;
        int j = SA[r - 1];
        const unsigned char *a = S + i + k;
        const unsigned char *b = S + j + k;
        while (*a == *b) { a++; b++; k++; }
        H[r] = k;
    }

    char *p = outbuf;
    for (int i = 0; i < n; i++) p = wint(p, SA[i] + 1, (i == n - 1) ? '\n' : ' ');
    for (int i = 1; i < n; i++) p = wint(p, H[i], (i == n - 1) ? '\n' : ' ');
    if (n == 1) *p++ = '\n';
    fwrite(outbuf, 1, p - outbuf, stdout);
    return 0;
}

评测结果