代码

#include <bits/stdc++.h>

using namespace std;

struct fast_IO{
    /***read***/
    char buf[1000000], *s = buf, *t = buf;
    inline char gc()
    {
        #ifdef LOCAL
        return getchar();
        #endif
        return s == t && (t = (s = buf) + fread(buf, 1, 1000000, stdin), s == t) ? EOF : *s ++ ;
    }

    // read a character
    int chtype = 0;
    inline void chnormal() {chtype = 0;}
    inline void chall() {chtype = 1;}
    inline void chdigit() {chtype = 2;}
    inline void chletter() {chtype = 3;}
    inline char chread()
    {
        char ch = gc();
        while(ch != EOF && ch <= 32) ch = gc();
        return ch;
    }
    inline char digitread()
    {
        char ch = gc();
        while(ch != EOF && (ch < '0' || ch > '9')) ch = gc();
        return ch;
    }
    inline char letterread()
    {
        char ch = gc();
        while(ch != EOF && !('A' <= ch && ch <= 'Z' || 'a' <= ch && ch <= 'z')) ch = gc();
        return ch;
    }

    // read a string
    int strtype = 0;
    inline void strnormal() {strtype = 0;}
    inline void strline() {strtype = 1;}
    inline void strread(char *s)
    {
        char ch = gc();
        while(ch <= 32) ch = gc();
        while(ch > 32) *s ++ = ch, ch = gc();
        *s = 0;
    }
    inline void lineread(char *s)
    {
        char ch = gc();
        while(ch < 32) ch = gc();
        while(ch >= 32) *s ++ = ch, ch = gc();
        *s = 0;
    }

    // read an integer
    int inttype = 0;
    inline void intnormal() {inttype = 0;}
    inline void intunsigned() {inttype = 1;}
    int lltype = 0;
    inline void llnormal() {lltype = 0;}
    inline void llunsigned() {lltype = 1;}
    template <typename T>
    inline void uread(T &x)
    {
        char ch = gc();
        x = 0;
        while(ch < '0' || ch > '9') ch = gc();
        while('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    }
    template <typename T>
    inline void read(T &x)
    {
        char ch = gc();
        x = 0;
        bool f = 0;
        while(ch < '0' || ch > '9')
        {
            if(ch == '-') f = 1;
            ch = gc();
        }
        if(f) while('0' <= ch && ch <= '9') x = x * 10 - (ch ^ 48), ch = gc();
        else while('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
    }

    // read a real number
    template <typename T>
    inline void dread(T &x)
    {
        char ch = gc();
        x = 0;
        int f = 1;
        while(ch < '0' || ch > '9')
        {
            if(ch == '-') f = -1;
            ch = gc();
        }
        while('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
        if(ch == '.')
        {
            ch = gc();
            double p = 0.1;
            while('0' <= ch && ch <= '9') x += p * (ch ^ 48), ch = gc(), p *= 0.1;
        }
        x *= f;
    }

    inline fast_IO & operator >> (char &x)
    {
        switch(chtype)
        {
            case 0 : x = chread(); break ;
            case 1 : x = gc(); break ;
            case 2 : x = digitread(); break ;
            case 4 : x = letterread(); break ;
            default : break ;
        }
        return *this;
    }
    inline fast_IO & operator >> (char *x)
    {
        strtype ? lineread(x) : strread(x);
        return *this;
    }
    inline fast_IO & operator >> (string &x)
    {
        static char buf[1000005];
        strtype ? lineread(buf) : strread(buf);
        return x = buf, *this;
    }
    inline fast_IO & operator >> (int &x)
    {
        inttype ? uread(x) : read(x);
        return *this;
    }
    inline fast_IO & operator >> (unsigned &x)
    {
        return uread(x), *this;
    }
    inline fast_IO & operator >> (long long &x)
    {
        lltype ? uread(x) : read(x);
        return *this;
    }
    inline fast_IO & operator >> (unsigned long long &x)
    {
        return read(x), *this;
    }
    inline fast_IO & operator >> (__int128 &x)
    {
        lltype ? read(x) : read(x);
        return *this;
    }
    inline fast_IO & operator >> (unsigned __int128 &x)
    {
        return read(x), *this;
    }
    inline fast_IO & operator >> (float &x)
    {
        return dread(x), *this;
    }
    inline fast_IO & operator >> (double &x)
    {
        return dread(x), *this;
    }
    inline fast_IO & operator >> (long double &x)
    {
        return dread(x), *this;
    }
    inline fast_IO & operator >> (__float128 &x)
    {
        return dread(x), *this;
    }

    /***write***/
    char obuf[1000000], *p = obuf;
    const char endl = '\n';
    inline void pc(char x)
    {
        p - obuf < 1000000 ? (*p ++ = x) : (fwrite(obuf, p - obuf, 1, stdout), p = obuf, *p ++ = x);
    }
    inline ~fast_IO() {fwrite(obuf, p - obuf, 1, stdout);}
    template <typename T>
    inline void write(T x)
    {
        if(!x) return pc(48);
        int len = 0;
        static char c[40];
        if(x < 0) pc('-'), x = -x;
        while(x) c[ ++ len] = (x % 10) ^ 48, x /= 10;
        while(len) pc(c[len -- ]);
    }
    inline fast_IO & operator << (int x)
    {
        return write(x), *this;
    }
    inline fast_IO & operator << (unsigned x)
    {
        return write(x), *this;
    }
    inline fast_IO & operator << (long long x)
    {
        return write(x), *this;
    }
    inline fast_IO & operator << (unsigned long long x)
    {
        return write(x), *this;
    }
    inline fast_IO & operator << (__int128 x)
    {
        return write(x), *this;
    }
    inline fast_IO & operator << (unsigned __int128 x)
    {
        return write(x), *this;
    }
    inline fast_IO & operator << (char x)
    {
        return pc(x), *this;
    }
    inline fast_IO & operator << (char *x)
    {
        while(*x) pc(*x ++ );
        return *this;
    }
    inline fast_IO & operator << (string x)
    {
        for(char i : x) pc(i);
        return *this;
    }
}IO;

const int N = 1e5 + 5;

int n, m;
char s[N];
int sa[N], sb[N], rnk[N], _rnk[N], cnt[N], hight[N];

inline void Sort()
{
	m = 127;
	for(int i = 1; i <= n; i ++ ) cnt[s[i]] ++ ;
	for(int i = 1; i <= m; i ++ ) cnt[i] += cnt[i - 1];
	for(int i = n; i >= 1; i -- ) sa[cnt[s[i]] -- ] = i;
	for(int i = 1; i <= m; i ++ ) cnt[i] = 0;
	m = 0;
	for(int i = 1; i <= n; i ++ ) rnk[sa[i]] = m += s[sa[i]] != s[sa[i - 1]];
	for(int len = 1; m < n; len <<= 1)
	{
		int k;
		for(k = 1; k <= len; k ++ ) sb[k] = n - len + k;
		for(int i = 1; i <= n; i ++ ) if(sa[i] > len) sb[k ++ ] = sa[i] - len;
		for(int i = 1; i <= n; i ++ ) cnt[rnk[i]] ++ ;
		for(int i = 1; i <= m; i ++ ) cnt[i] += cnt[i - 1];
		for(int i = n; i >= 1; i -- ) sa[cnt[rnk[sb[i]]] -- ] = sb[i];
		for(int i = 1; i <= m; i ++ ) cnt[i] = 0;
		m = 0;
		for(int i = 1; i <= n; i ++ ) _rnk[sa[i]] = m += rnk[sa[i]] != rnk[sa[i - 1]] || rnk[sa[i] + len] != rnk[sa[i - 1] + len];
		for(int i = 1; i <= n; i ++ ) rnk[i] = _rnk[i];
	}
}
inline void Hight()
{
	for(int i = 1, len = 0; i <= n; i ++ )
	{
		int j = sa[rnk[i] - 1];
		if(len) len -- ;
		while(s[i + len] == s[j + len]) len ++ ;
		hight[rnk[i]] = len;
	}
}

int main()
{
	IO >> s + 1;
	n = strlen(s + 1);
	Sort(), Hight();
	for(int i = 1; i <= n; i ++ ) IO << sa[i] << char(32);
	IO << char(10);
	for(int i = 2; i <= n; i ++ ) IO << hight[i] << char(32);
	return 0;
}

评测结果