代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

int OutN;
char Out[10000000];
int tmpOutN;
char tmpOut[20];

template<class T>
inline void write(T x) {
    if(x < 0) x = -x, Out[OutN++] = '-';
    if(x) {
        tmpOutN = 0;
        while(x) {
            tmpOut[tmpOutN++] = x%10+'0';
            x /= 10;
        }
        while(tmpOutN--) Out[OutN++] = tmpOut[tmpOutN];
    }
    else Out[OutN++] = '0';
}

const int N = 200009;
const int SIGMA = 26;

int n;
char str[N];
int sa[N], tot;
int rk[N], h[N];

struct Edge {
    int u, v, c;

    Edge() {u = v = 0;}
    Edge(int _u, int _v, int _c) {u = _u, v = _v, c = _c;}
}e[N];
int eN;

struct Tree {
    int sz, head[N], to[N], ne[N];

    Tree() {
        sz = 1;
        memset(head, 0, sizeof head);
    }

    inline void addEdge(int u, int v) {
        to[sz] = v, ne[sz] = head[u], head[u] = sz++;
    }
}T;

struct SAM {
    int root, sz, last, fa[N], maxl[N], right[N], ne[N][SIGMA], pos[N];
    
    SAM() {
        sz = root = last = 1, fa[1] = maxl[1] = 0;
        memset(ne[1], 0, sizeof ne[1]);
    }
    
    inline int newNode(int l) {
        maxl[++sz] = l, fa[sz] = 0;
        memset(ne[sz], 0, sizeof ne[sz]);
        return sz;
    }
    
    inline void add(int x, int i) {
        int p = last, np = newNode(maxl[p]+1);
        while(p && !ne[p][x])
            ne[p][x] = np, p = fa[p];
        if(!p) fa[np] = root;
        else {
            int q = ne[p][x];
            if(maxl[q] == maxl[p]+1) fa[np] = q;
            else {
                int r = newNode(maxl[p]+1);
                memcpy(ne[r], ne[q], sizeof ne[r]);
                fa[r] = fa[q], right[r] = right[q], fa[q] = fa[np] = r;
                while(p && ne[p][x] == q)
                    ne[p][x] = r, p = fa[p];
            }
        }
        right[np] = maxl[np], pos[np] = i, last = np;
    }

    inline int get(int x, int y) {
        return str[n-right[y]+1+maxl[x]]-'a';
    }
    
    inline void construct() {
        static int cnt[SIGMA], top[N];
        for(int i = 2; i <= sz; ++i) {
            e[++eN] = Edge(fa[i], i, get(fa[i], i));
            cnt[e[eN].c]++;
        }
        for(int i = 1; i < SIGMA; ++i) cnt[i] += cnt[i-1];
        for(int i = 1; i <= eN; ++i) top[cnt[e[i].c]--] = i;
        for(int i = eN; i >= 1; --i) T.addEdge(e[top[i]].u, e[top[i]].v);
    }

    void dfs(int now) {
        if(pos[now]) sa[++tot] = pos[now];
        for(int i = T.head[now]; i; i = T.ne[i])
            dfs(T.to[i]);
    }
}sam;


inline void init() {
    scanf("%s", str+1);
}

inline void solve() {
    n = strlen(str+1);
    for(int i = n; i >= 1; --i)
        sam.add(str[i]-'a', i);
    sam.construct(), sam.dfs(1);
    for(int i = 1; i <= n; ++i) rk[sa[i]] = i;
    for(int i = 1, k = 0; i <= n; ++i) {
        if(k) k--;
        int j = sa[rk[i]-1];
        while(str[i+k] == str[j+k]) k++;
        h[rk[i]] = k;
    }
    for(int i = 1; i <= n; ++i)
        write(sa[i]), Out[OutN++] = i==n?'\n':' ';
    for(int i = 2; i <= n; ++i)
        write(h[i]), Out[OutN++] = i==n?'\n':' ';
    fwrite(Out, sizeof(char), OutN, stdout);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    init();
    solve();
    
#ifndef ONLINE_JUDGE
    fclose(stdin);fclose(stdout);
#endif
    return 0;
}

评测结果