文件详细信息

下载本文件

本文件的大小为 1028 字节。

//$O(n \times 2^n)$
#include<cstdio>
#include<cstring>
const int maxlog2n=18,maxn=1<<maxlog2n;
int log2n,n,m;
char s[maxn+1];
int sa[maxn],rk[maxn<<1],oldrk[maxn<<1],id[maxn],cnt[maxn];
int main(){
	scanf("%d%s",&log2n,s);
	n=1<<log2n;
	m=n>26?n:26;
	for(int i=0;i<n;i++)cnt[rk[i]=s[i]-'a']++;
	for(int i=1;i<m;i++)cnt[i]+=cnt[i-1];
	for(int i=n-1;i>=0;i--)sa[--cnt[rk[i]]]=i;
	for(int w=1;w<n;w<<=1){
		memset(cnt,0,sizeof(int)*m);
		for(int i=0;i<n;i++)cnt[rk[(id[i]=sa[i])^w]]++;
		for(int i=1;i<m;i++)cnt[i]+=cnt[i-1];
		for(int i=n-1;i>=0;i--)sa[--cnt[rk[id[i]^w]]]=id[i];
		memset(cnt,0,sizeof(int)*m);
		for(int i=0;i<n;i++)cnt[rk[id[i]=sa[i]]]++;
		for(int i=1;i<m;i++)cnt[i]+=cnt[i-1];
		for(int i=n-1;i>=0;i--)sa[--cnt[rk[id[i]]]]=id[i];
		memcpy(oldrk,rk,sizeof(int)*n);
		int p=0;
		for(int i=0;i<n;i++)
			if(i==0||(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]^w]==oldrk[sa[i-1]^w]))rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		m=p+1;
		if(p==n)break;
	}
	for(int i=0;i<n;i++)putchar(s[i^sa[0]]);
	putchar('\n');
	return 0;
}