代码

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
 
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;

template<typename T> inline void MAX(T &a, T b) { if(b > a) a = b; }

const int N = 1e6 + 100;

int n, m;
char s[N];
int sa[N], ary1[N], ary2[N], *rk = ary1, *ass = ary2, cnt[N];
int dif[N], tm[N], dp, ans[N];
bool vis[N];

int main() {
	scanf("%s", s + 1);
	n = (int)strlen(s + 1);
	
	for(int i = 1; i <= n; ++i) ++cnt[s[i]], MAX(m, (int)s[i]);
	for(int i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
	for(int i = 1; i < m; ++i) {
		int x = cnt[i] + 1;
		vis[x] = true;
	}
	for(int i = n; i >= 1; --i) s[i][cnt]--[sa] = i;
	m = 0;
	for(int i = 1; i <= n; ++i) {
		sa[i][rk] = (sa[i][s] != sa[i - 1][s] ? ++m : m);
	}
	
	for(int j = 1; m < n; j <<= 1) {
		for(int i = n - j + 1, p = 1; i <= n; ++i, ++p) ass[p] = i;
		for(int i = 1, p = j; i <= n; ++i) if(sa[i] > j) ass[++p] = sa[i] - j;
		for(int i = 1; i <= m; ++i) cnt[i] = 0;
		for(int i = 1; i <= n; ++i) ass[i][rk][cnt]++;
		for(int i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
		for(int i = n; i >= 1; --i) ass[i][rk][cnt]--[sa] = ass[i];
		m = 0, swap(rk, ass);
		for(int i = 1; i <= n; ++i) {
			sa[i][rk] = (sa[i][ass] != sa[i - 1][ass] || sa[i] + j > n || (sa[i] + j)[ass] != (sa[i - 1] + j)[ass] ? ++m : m);
			if(!vis[i] && sa[i][rk] != sa[i - 1][rk]) ans[i] = j + ans[rk[sa[i] + j]], vis[i] = true;
		}
	}
	for(int i = 1; i <= n; ++i) printf("%d ", sa[i]);
	putchar('\n');
	
	// for(int i = 1; i <= dp; ++i) {
	// 	int x = dif[i], j = tm[i];
	// 	ans[x] = j + ans[x + j];
	// }
	for(int i = 2; i <= n; ++i) printf("%d ", ans[i]);
	return 0;
}

评测结果