代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
void iopen()
{
    static bool isOpen = false;
    if (!isOpen) {
        isOpen = true;
#ifdef MDEBUG
        freopen("in.txt", "r", stdin);
#endif
    }
}
template <size_t _I_Buffer_Size = 1 << 23, size_t _O_Buffer_Size = 1 << 23>
struct IO_Tp
{
    char _I_Buffer[_I_Buffer_Size];
    char *_I_pos;

    char _O_Buffer[_O_Buffer_Size];
    char *_O_pos;

    IO_Tp()
        : _I_pos(_I_Buffer)
        , _O_pos(_O_Buffer)
    {
        iopen();
        fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
    }

    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    inline bool is_digit(const char ch) { return '0' <= ch && ch <= '9'; }

    template<typename Int>
    inline IO_Tp &operator>>(Int &res)
    {
        res = 0;
		int k=1;
		while (!is_digit(*_I_pos)) {
			if (*_I_pos=='-')
				k=-1;
            _I_pos++;
		}
        do
            (res *= 10) += (*_I_pos++) & 15;
        while (is_digit(*_I_pos));
		res*=k;
        return *this;
    }


    inline char getop()
    {
        while (!is_digit(*_I_pos))
            _I_pos++;
        return (*_I_pos++) & 15;
    }

    template<typename Int>
    inline IO_Tp &operator<<(Int n)
    {
        if (n < 0) {
            *_O_pos++ = '-';
            n = -n;
        }
        static char _buf[20];
        char *_pos(_buf);
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf)
            *_O_pos++ = *--_pos;
        return *this;
    }

    inline IO_Tp &operator<<(char ch)
    {
        *_O_pos++ = ch;
        return *this;
    }
};
// IO_Tp<> IO;
#define MAXN 100000
struct Data
{
	int a,b,id;
}x[MAXN+10];
bool comp(const Data& a,const Data& b)
{
	if (a.a==b.a && a.b==b.b) return a.id<b.id;
	if (a.a==b.a) return a.b<b.b;
	return a.a<b.a;
}
int n;
char a[MAXN+10];
int sa[MAXN+10],rk[2*MAXN+10];
void calcSA()
{
	for(int i=1; i<=n; ++i) {
		x[i].a=a[i];
		x[i].b=0;
		x[i].id=i;
	}
	int p=0;
	for(int i=1;p<n;i*=2) {
		p=0;
		sort(x+1,x+1+n,comp);
		Data t={0,0,0};
		for(int j=1; j<=n; ++j) {
			if (x[j].a!=t.a || x[j].b!=t.b) {
				++p;
				t=x[j];
			}
			rk[x[j].id]=p;
		}
		for(int j=1; j<=n; ++j) {
			x[j].a=rk[j];
			x[j].b=rk[j+i];
			x[j].id=j;
		}
	}
	for(int i=1; i<=n; ++i) {
		sa[rk[i]]=i;
	}
}
int height[MAXN+10];
void calcHeight()
{
	int k=0;
	for(int i=1; i<=n; ++i) {
		k=max(k-1,0);
		int j=sa[rk[i]-1];
		while(a[i+k]==a[j+k]) ++k;
		height[rk[i]]=k;
	}
}
int main()
{
	iopen();
	scanf("%s",a+1);
	n=strlen(a+1);
	calcSA();
	calcHeight();
	for(int i=1; i<=n; ++i) {
		printf("%d ",sa[i]);
	}
	puts("");
	for(int i=2; i<=n; ++i) {
		printf("%d ",height[i]);
	}
	puts("");
    return 0;
}

评测结果