代码

#include <bits/stdc++.h>
using namespace std;
#define MAXN 200000
#define c(x,y) t[x].c[y]
#define maxlen(x) t[x].maxlen
#define link(x) t[x].link
#define mx(x) t[x].mx
#define end(x) t[x].end
#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[26],maxlen,link,end; bool mx;}t[MAXN+5]; int first[MAXN+5], start, tot, last, n, rk;
#define New(p,w,i) (++tot, first[tot] = -1, maxlen(tot) = p?maxlen(p)+1:0, mx(tot) = w, end(tot) = i, tot)
struct Edge{int to,nex; Edge(){} Edge(int _to, int _nex):to(_to),nex(_nex){}}e[MAXN+5]; int etot;
inline void Add(int a, int b){e[etot] = Edge(b,first[a]), first[a] = etot++;}
char s[(MAXN>>1)+5]; int book[26], w[MAXN+5], o[MAXN+5], SA[(MAXN>>1)+5], Rank[(MAXN>>1)+5], Height[(MAXN>>1)+5];
inline void Append(int x, int i)
{
	rint p = last, np = last = New(p,1,i), q, nq; for(; p && !c(p,x); c(p,x) = np, p = link(p));
	if(!p) link(np) = start; else if(maxlen(q=c(p,x))==maxlen(p)+1) link(np) = q;
	else
	{
		for(nq = New(p,0,i), memcpy(t[nq].c,t[q].c,104); p && c(p,x)==q; c(p,x) = nq, p = link(p));
		link(nq) = link(q), link(q) = link(np) = nq;
	}
}
void DFS(int p){mx(p) ? SA[Rank[end(p)]=++rk] = end(p) : 0; for(rint u = first[p], v; ~u; DFS(e[u].to), 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()
{
	start = 1, New(0,0,0), scanf("%s",s+1), n = strlen(s+1); last = 1; for(rint i = n; i; Append(s[i]-'a',i), i--); book[0] = 1;
	for(rint i = 2; i <= tot; ++book[w[i]=s[end(i)+maxlen(link(i))]-'a'], i++); for(rint i = 1; i < 26; book[i] += book[i-1], i++);
	for(rint i = tot; i; o[book[w[i]]--] = i, i--); for(rint i = tot; i>1; Add(link(o[i]),o[i]), i--); DFS(1); 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;
}

评测结果