代码

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define INF 0x3f3f3f3f
#define c(x,y) t[x].c[y]
#define beg(x) t[x].beg
#define len(x) t[x].len
#define link(x) t[x].link
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
#define BUF_SIZE 1000000
#define _END fwrite(_Ob,1,_O-_Ob,stdout), _O = _Ob
#define oc(a) (*_O++ = a)
char _Ob[BUF_SIZE+5], *_O = _Ob, _Os[25], *_Ot;
inline void os(string s){_O += s.copy(_O,s.length(),0), _O-_Ob >= BUF_SIZE-50 ? _END : 0;}
template <typename T> inline void oi(T x)
{
	if(!x){oc('0'); return;} if(x < 0) oc('-'), x = -x;
	for(_Ot = _Os; x; *_Ot++ = x%10+'0', x /= 10);
	for(; _Ot != _Os; oc(*--_Ot)); _O-_Ob >= BUF_SIZE-50 ? _END : 0;
}
struct Node{int c[27],beg,len,link;}t[(MAXN<<1)+5]; int s[MAXN+5], SA[MAXN+5], Rank[MAXN+5], Height[MAXN+5], n, m, tot, last, rem; char str[MAXN+5];
#define New(b,l) (++tot, beg(tot) = b, len(tot) = l, fir[tot] = -1, link(tot) = 1, tot)
struct Edge{int to,nex; Edge(){} Edge(int _to, int _nex):to(_to),nex(_nex){}}e[(MAXN<<2)+5]; int fir[(MAXN<<1)+5], fa[(MAXN<<1)+5], o[(MAXN<<1)+5], book[27], etot, rk;
inline void Add(int a, int b){e[etot] = Edge(b,fir[a]), fir[a] = etot++;}
inline void Append(int x){
	for(int q = (s[++m]=x,++rem,1), nq; rem; last>1?last=link(last):--rem){
		for(; rem > len(c(last,s[m-rem+1])); rem -= len(last=c(last,s[m-rem+1]))); int &p = c(last,s[m-rem+1]);
		if(!p) p = New(m-rem+1,INF), q = link(q) = last; else if(x==s[beg(p)+rem-1]){q = link(q) = last; break;}
		else nq = New(beg(p),rem-1), c(nq,x) = New(m,INF), c(nq,s[beg(p)+=rem-1]) = p, len(p) -= rem-1, q = link(q) = p = nq;
	}
}
void DFS(int p, int d){if(len(p)>n) SA[Rank[beg(p)-d]=rk++] = beg(p)-d; else{d += len(p); for(rint u = fir[p]; ~u; DFS(e[u].to,d), u = e[u].nex);}}
void CalHeight(){for(rint i = 1, L = 0, j; i <= n; Height[Rank[i++]] = L) for(j = SA[~-Rank[i]], L-=L>0; i+L<=n&&j+L<=n&&s[i+L]==s[j+L]; ++L);}
int main(){
	scanf("%s",str+1); n = strlen(str+1); last = ++tot; len(0) = INF; for(rint i = 1; i <= n; Append(str[i]-'a'+1), i++);
	Append(0); for(rint i = 1, j; i <= tot; i++) for(j = 0; j <= 26; c(i,j)?fa[c(i,j)]=i:0, j++); memset(fir+1,-1,tot<<2);
	book[0] = 1; for(rint i = 2; i <= tot; ++book[s[beg(i)]], i++); for(rint i = 1; i <= 26; book[i] += book[i-1], i++);
    for(rint i = tot; i; o[book[s[beg(i)]]--] = i, i--); for(rint i = tot; i>1; Add(fa[o[i]],o[i]), i--); DFS(1,0); CalHeight();
    for(rint i = 1; i <= n; oi(SA[i]), oc(' '), i++); oc('\n');
	for(rint i = 2; i <= n; oi(Height[i]), oc(' '), i++); oc('\n'); _END; return 0;
}

评测结果