【BZOJ2882】工艺（后缀数组）

时间：2023-03-09 01:10:47
【BZOJ2882】工艺（后缀数组）

【BZOJ2882】工艺（后缀数组）

题面

BZOJ权限题，我爱良心洛谷

题解

最容易的想法：

把字符串在后面接一份

然后求后缀数组就行了。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 620000

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n;

int SA[MAX],a[MAX],x[MAX],y[MAX],t[MAX];

bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}

void GetSA()

{

	int m=n;

	for(int i=1;i<=n+n;++i)t[x[i]=a[i]]++;

	for(int i=1;i<=m;++i)t[i]+=t[i-1];

	for(int i=n+n;i;--i)SA[t[x[i]]--]=i;

	for(int k=1;k<=n+n;k<<=1)

	{

		int p=0;

		for(int i=n+n-k+1;i<=n+n;++i)y[++p]=i;

		for(int i=1;i<=n+n;++i)if(SA[i]>k)y[++p]=SA[i]-k;

		for(int i=0;i<=m;++i)t[i]=0;

		for(int i=1;i<=n+n;++i)t[x[y[i]]]++;

		for(int i=1;i<=m;++i)t[i]+=t[i-1];

		for(int i=n+n;i;--i)SA[t[x[y[i]]]--]=y[i];

		swap(x,y);

		x[SA[1]]=p=1;

		for(int i=2;i<=n+n;++i)

			x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;

		if(p>=n)break;

		m=p;

	}

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=a[i+n]=read();

	n=n;

	GetSA();

	for(int i=1;i<=n+n;++i)

	{

		if(SA[i]<=n)

		{

			for(int j=0;j<n;++j)printf("%d ",a[SA[i]+j]);

			puts("");

			break;

		}

	}

	return 0;

}

相关文章