【Luogu5108】仰望半月的夜空（后缀数组）

时间：2023-03-09 04:38:25
【Luogu5108】仰望半月的夜空（后缀数组）

【Luogu5108】仰望半月的夜空（后缀数组）

题面

洛谷

题解

实名举报这题在比赛之前还不是这个样子的，还被我用SAM给水过去了

很明显求出\(SA\)之后就是按照\(SA\)的顺序从前往后考虑每一个长度，这样可以知道串是什么。

不过如果串相同要左端点最靠左，所以二分包含这个串的区间，用\(RMQ\)求出区间最小值即可。

（其实就是拿来复习SA板子的）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAX 400200

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

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

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

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

	return t?-x:x;

}

int n,sig;

char ch[MAX];

int S[MAX],tot,a[MAX],lg[MAX];

int t[MAX],x[MAX],y[MAX],rk[MAX],SA[MAX],hg[20][MAX],mn[20][MAX];

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

void GetSA()

{

	int m=tot;

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

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

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

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

	{

		int 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)t[i]=0;

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

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

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

		swap(x,y);x[SA[1]]=p=1;

		for(int i=2;i<=n;++i)x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;

		if(p>=n)break;m=p;

	}

	for(int i=1;i<=n;++i)rk[SA[i]]=i;

	for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;

	for(int i=1,j=0;i<=n;++i)

	{

		if(j)--j;

		while(a[i+j]==a[SA[rk[i]-1]+j])++j;

		hg[0][rk[i]]=j;

	}

	for(int j=1;j<=lg[n];++j)

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

			hg[j][i]=min(hg[j-1][i],hg[j-1][i+(1<<(j-1))]);

	for(int i=1;i<=n;++i)mn[0][i]=SA[i];

	for(int j=1;j<=lg[n];++j)

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

			mn[j][i]=min(mn[j-1][i],mn[j-1][i+(1<<(j-1))]);

}

int lcp(int i,int j)

{

	if(i==j)return 1e9;i=rk[i];j=rk[j];

	if(i>j)swap(i,j);i+=1;int k=lg[j-i+1];

	return min(hg[k][i],hg[k][j-(1<<k)+1]);

}

int RMQ(int i,int j)

{

	if(i>j)swap(i,j);int k=lg[j-i+1];

	return min(mn[k][i],mn[k][j-(1<<k)+1]);

}

int main()

{

	sig=read();n=read();

	if(sig==26)

	{

		scanf("%s",ch+1);n=strlen(ch+1);

		for(int i=1;i<=n;++i)a[i]=ch[i]-96;

	}

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

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

	sort(&S[1],&S[n+1]);tot=unique(&S[1],&S[n+1])-S-1;

	for(int i=1;i<=n;++i)a[i]=lower_bound(&S[1],&S[tot+1],a[i])-S;

	GetSA();

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

	{

		while(n-SA[p]+1<i)++p;

		int l=p+1,r=n,ret=p;

		while(l<=r)

		{

			int mid=(l+r)>>1;

			if(lcp(SA[p],SA[mid])>=i)l=mid+1,ret=mid;

			else r=mid-1;

		}

		printf("%d ",RMQ(p,ret));

	}

	puts("");return 0;

}

相关文章