记录编号	566818	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	后缀数组	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	2.542 s
提交时间	2021-11-16 22:31:31	内存使用	8.43 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 300005;
char s[maxn];
int rk[maxn],sa[maxn],height[maxn],y[maxn],p,n,m,cnt[maxn];
int main() {
	freopen("sav.in","r",stdin);
	freopen("sav.out","w",stdout);
	scanf("%s",s + 1);
	n = strlen(s + 1);
	m = 300;
	for(int i = 1;i <= n;++ i)++ cnt[rk[i] = s[i]];
	for(int i = 2;i <= m;++ i)cnt[i] += cnt[i - 1];
	for(int i = n;i >= 1;-- i)sa[cnt[rk[i]] --] = i;
	for(int k = 1;k <= n;k <<= 1,m = p) {
		p = 0;
		for(int i = n - k + 1;i <= n;++ i) {
			y[++ p] = i;
		}
		for(int i = 1;i <= n;++ i) {
			if(sa[i] > k) {
				y[++ p] = sa[i] - k;
			}
		}
		for(int i = 1;i <= m;++ i)cnt[i] = 0;
		for(int i = 1;i <= n;++ i)++ cnt[rk[i]];
		for(int i = 2;i <= m;++ i)cnt[i] += cnt[i - 1];
		for(int i = n;i >= 1;-- i)sa[cnt[rk[y[i]]] --] = y[i],y[i] = 0;
		swap(rk , y);
		rk[sa[1]] = 1;
		p = 1;
		for(int i = 2;i <= n;++ i)rk[sa[i]] = y[sa[i]] == y[sa[i - 1]]&&y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++ p;
		if(p >= n)break ;
	} 
	for(int i = 1;i <= n;++ i)rk[sa[i]] = i;
	int j,k = 0;
	for(int i = 1;i <= n;++ i) {
		if(rk[i] == 1)continue ;
		if(k)-- k;
		j = sa[rk[i] - 1];
		while(s[i + k] == s[j + k]&&i + k <= n&&j + k <= n)++ k;
		height[rk[i]] = k;
	}
	for(int i = 1;i <= n;++ i) {
		printf("%d ",sa[i] - 1);
	}
	putchar('\n');
	for(int i = 1;i <= n;++ i) {
		printf("%d ",height[i]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0; 
}