代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
const int N = 200005;
namespace SA{
	int sa[N], hs[N], hr[N], rk[N];
	int tmp[N], bin[N];
	void build(char *S, int ls){
		int sz = max(ls, 255);
		rep(i, 1, ls) rk[i] = S[i];
		rep(i, 1, sz) bin[i] = 0;
		rep(i, 1, ls) ++bin[rk[i]];
		rep(i, 2, sz) bin[i] += bin[i - 1];
		rep(i, 1, ls) sa[--bin[rk[i]] + 1] = i;
		for(int j = 1; j <= ls; j <<= 1){
			int tot = 0;
			rep(i, ls - j + 1, ls) tmp[++tot] = i;
			rep(i, 1, ls) if(sa[i] - j > 0) tmp[++tot] = sa[i] - j;
			rep(i, 1, sz) bin[i] = 0;
			rep(i, 1, ls) ++bin[rk[i]];
			rep(i, 2, sz) bin[i] += bin[i - 1];
			per(i, ls, 1) sa[--bin[rk[tmp[i]]] + 1] = tmp[i];
			tot = 1; tmp[sa[1]] = 1;
			rep(i, 2, ls)
				tmp[sa[i]] = rk[sa[i]] == rk[sa[i - 1]] && rk[sa[i] + j] == rk[sa[i - 1] + j] ? tot : ++tot;
			rep(i, 1, ls) rk[i] = tmp[i];
			if(ls == tot) break;
		}
		rep(i, 1, ls){
			hs[i] = max(hs[i - 1] - 1, 0);
			while(S[i + hs[i]] == S[sa[rk[i] - 1] + hs[i]]) ++hs[i];
			hr[rk[i]] = hs[i];
		}
	}
}
char S[N];
int main(){
	scanf("%s", S + 1);
	int ls = strlen(S + 1);
	SA::build(S, ls);
	rep(i, 1, ls) printf("%d ", SA::sa[i]);
	puts("");
	rep(i, 2, ls) printf("%d ", SA::hr[i]);
}

评测结果