代码

#include <cstdio>
#include <cstring>

static const int MAXN = 100010;

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

static void induce(int *s, unsigned char *t, int *sa, int n, int K,
                   int *SL, int *SS, int *BUF, const int *lms, int m) {
    for (int i = 0; i < n; i++) sa[i] = -1;
    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;
    }
}

// build SA of s[0..n-1], values in [0, K-1], K = number of buckets (>=2)
static void sais(int *s, int *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 = new unsigned char[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 = new int[K + 1];
    int *SS = new int[K + 1];
    int *BUF = new int[K + 1];
    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 = new int[n + 1];
    for (int i = 0; i <= n; i++) LMSMAP[i] = -1;
    int m = 0;
    for (int i = 1; i < n; i++) {
        if (!t[i - 1] && t[i]) LMSMAP[i] = m++;
    }
    int *LMS = new int[m];
    {
        int p = 0;
        for (int i = 1; i < n; i++) if (!t[i - 1] && t[i]) LMS[p++] = i;
    }

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

    if (m) {
        int *SLMS = new int[m];
        {
            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 = new int[m];
        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 = new int[m];
        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);
        delete[] SLMS;
        delete[] RS;
        delete[] RSA;
    }

    delete[] t;
    delete[] SL;
    delete[] SS;
    delete[] BUF;
    delete[] LMSMAP;
    delete[] LMS;
}

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

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

    sais(S, SA, n, 26);

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

    int k = 0;
    for (int i = 0; i < n; i++) {
        if (RANK[i] == 0) { k = 0; continue; }
        if (k) k--;
        int j = SA[RANK[i] - 1];
        while (i + k < n && j + k < n && S[i + k] == S[j + k]) k++;
        H[RANK[i]] = k;
    }

    char *p = outbuf;
    for (int i = 0; i < n; i++) {
        int v = SA[i] + 1;
        char tmp[8];
        int c = 0;
        do { tmp[c++] = '0' + v % 10; v /= 10; } while (v);
        while (c) *p++ = tmp[--c];
        *p++ = (i == n - 1) ? '\n' : ' ';
    }
    for (int i = 1; i < n; i++) {
        int v = H[i];
        char tmp[8];
        int c = 0;
        do { tmp[c++] = '0' + v % 10; v /= 10; } while (v);
        while (c) *p++ = tmp[--c];
        *p++ = (i == n - 1) ? '\n' : ' ';
    }
    if (n == 1) *p++ = '\n';
    fwrite(outbuf, 1, p - outbuf, stdout);
    return 0;
}

评测结果