【BZOJ1031】字符加密

    字符串延长一倍后算出它的后缀数组，然后选择sa[i]<=n的加入答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;

int sa[maxn<<1];
char s[maxn<<1],ans[maxn];
int n,ansn;

int c[maxn<<1],t1[maxn<<1],t2[maxn<<1];

void Build_SA()
{
	int i,m=255,*x=t1,*y=t2;
	for (i=0;i<=m;i++) c[i]=0;
	for (i=1;i<=n;i++) c[x[i]=s[i]]++;
	for (i=1;i<=m;i++) c[i]+=c[i-1];
	for (i=n;i;i--) sa[c[x[i]]--]=i;
	for (int k=1;k<=n;k<<=1)
	{
		int p=0;
		for (i=n-k+1;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++) if (sa[i]>k) y[++p]=sa[i]-k;
		for (i=0;i<=m;i++) c[i]=0;
		for (i=1;i<=n;i++) c[x[y[i]]]++;
		for (i=1;i<=m;i++) c[i]+=c[i-1];
		for (i=n;i;i--) sa[c[x[y[i]]]--]=y[i];
		swap(x,y);p=1;x[sa[1]]=1;
		for (i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
		if (p>=n) break;
		m=p;
	}
}

int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for (int i=n+1;i<=(n<<1);i++) s[i]=s[i-n];
	n<<=1;
	Build_SA();
	for (int i=1;i<=n;i++) if (sa[i]<=(n>>1)) ans[++ansn]=s[sa[i]+(n>>1)-1];
	printf("%s\n",ans+1);
	return 0;
}