代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <numeric>

namespace IO {
    template <typename _T>
    inline bool read (_T& x) {
        x = 0;
        _T y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-') y = -1;
            c = getchar();
        }
        if (c == EOF) return false;
        while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
        x *= y;
        return true;
    }

    template <typename _T>
    inline _T input () {
        _T x = 0, y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-') y = -1;
            c = getchar();
        }
        if (c == EOF) return 0;
        while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
        x *= y;
        return x;
    }
};
using namespace IO;

#define reg register
#define MAX_N 200007
#define rep(i, l, r) for(int i = l; i <= r; ++i)
#define lep(i, l, r) for(int i = l; i < r; ++i)
#define irep(i, r, l) for(int i = r; i >= l; --i)
#define ilep(i, r, l) for(int i = r; i > l; --i)
typedef long long ll;

struct SuffixArray {
    int s[MAX_N << 1], sa[MAX_N], rank[MAX_N], height[MAX_N], pos[MAX_N], t[MAX_N];
    int buc[MAX_N << 1], cntb[MAX_N << 1];
    bool sml[MAX_N << 1];

    inline void IS (int n, int m, int *s, int *t, bool *sml, int n1) {
        // printf("asdas %d\n", sml[55]);
        memset(sa + 1, 0, n << 2);
        memset(buc + 1, 0, m << 2);
        rep (i, 1, n) buc[s[i]]++;
        std::partial_sum(buc + 1, buc + m + 1, cntb + 1); //前缀和
        irep (i, n1, 1) sa[cntb[s[t[i]]]--] = t[i];
        std::partial_sum(buc, buc + m + 1, cntb + 1);
        // printf("N, M: %d %d\n", m, n);
        
        // rep (i, 1, n) printf("%d ", sa[i]); puts("");puts("------------");
        // rep (i, 1, n) printf("%d ", s[i]); puts(""); puts("");
        // rep (i, 1, m) printf("%d ", cntb[i]); puts("");
        rep (i, 1, n) if (sa[i] > 1 && !sml[sa[i] - 1])
            // printf("%d %d\n", sa[i] - 1, cntb[s[sa[i] - 1]] + 1),
            sa[++cntb[s[sa[i] - 1]]] = sa[i] - 1;
        // puts("----------------------");
        // rep (i, 1, n) printf("%d ", cntb[i]); puts("");
        std::partial_sum(buc + 1, buc + m + 1, cntb + 1);
        irep (i, n, 1) if (sa[i] > 1 && sml[sa[i] - 1])
            sa[cntb[s[sa[i] - 1]]--] = sa[i] - 1;
    }

    void SAIS (int *s, bool *sml, int *t, int n, int m) {
        // puts("sadjkahdksa");
        int n1 = 0, m1 = 0, *s1 = s + n;
        sml[n] = true;
        irep (i, n - 1, 1) sml[i] = (s[i] == s[i + 1] ? sml[i + 1] : s[i] < s[i + 1]);
        // printf("%d %d %d\n", s[55], s[56], sml[55]);
        rep (i, 2, n) pos[i] = ((!sml[i - 1] && sml[i]) ? t[++n1] = i, n1 : 0);
        // rep (i, 1, n1) printf("%d ", sml[i]); puts("");
        // rep (i, 1, n) printf("%d ", s[i]); puts("");
        IS(n, m, s, t, sml, n1);
        // rep (i, 1, n) printf("%d ", sa[i]); puts("");
        for (int i = 1, x, y = 0; i <= n; ++i) if (x = pos[sa[i]]) {
                if (m1 <= 1 || t[x + 1] - t[x] != t[y + 1] - t[y])
                    m1++;
                else {
                    for (int j = t[x], k = t[y]; j <= t[x + 1]; ++j, ++k)
                        if (s[j] != s[k]) { m1++; break; }
                }
                s1[y = x] = m1;
            }
        // printf("%d %d\n", n1, m1);
        // rep (i, 1, n1) printf("%d ", s1[i]); puts("");
        if (m1 < n1) SAIS(s1, sml + n, t + n, n1, m1);
        else rep (i, 1, n1) sa[s1[i]] = i;
        rep (i, 1, n1) s1[i] = t[sa[i]];
        IS(n, m, s, s1, sml, n1);
    }

    inline void build (int *S, int N, int M) {
        s[++N] = 1;
        // rep (i, 1, N) printf("%d ", S[i]); puts("");
        SAIS(S, sml, t, N, M);
        // rep (i, 1, N) printf("%d ", sa[i]); puts("");
        rep (i, 1, N - 1) sa[i] = sa[i + 1];
    }

    inline void getHeight (int n) {
        // rep (i, 1, n) printf("%d ", s[i]); puts("");
        rep (i, 1, n) rank[sa[i]] = i;
        for (int i = 1, j, k = 0; i <= n; ++i) {
            if (k) k--;
            j = sa[rank[i] - 1];
            while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
            // printf("%d %d %d %d %d\n", i, j, k, s[i + k + 1], s[j + k + 1]);
            height[rank[i]] = k;
        }
        height[1] = 0;
    }
}SA;

char s[MAX_N];

int main () {
#ifndef ONLINE_JUDGE
    freopen ("in", "r", stdin);
#endif
    scanf("%s", s + 1);
    int N = strlen(s + 1);
    rep (i, 1, N) SA.s[i] = s[i] - 'a' + 2;
    SA.build(SA.s, N, 27);
    SA.getHeight(N);
    rep (i, 1, N) printf("%d ", SA.sa[i]); puts("");
    rep (i, 2, N) printf("%d ", SA.height[i]); puts("");
    return 0;
}

评测结果