为啥RE啊,求助
查看原帖
为啥RE啊,求助
123384
tommy0221楼主2020/5/19 19:57

谔谔我,写了SA。

这题由于全是小写字母,于是我调小了字符集 m 的大小,从122调到了26,同时把字符都减了 'a'-1,然后就RE了,代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rint int
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
inline int rd() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return x*f;
}
const int N=250010;
int m=26,t[30],x[N],y[N],n,sa[N],rk[N],height[N];
int ans[N],top,st[N],lp[N],rp[N];
char s[N];
void get_SA() {
	for(rint i=1;i<=m;++i)t[i]=0;
	for(rint i=1;i<=n;++i)++t[x[i]=(s[i]-'a'+1)];
	for(rint i=1;i<=m;++i)t[i]+=t[i-1];
	for(rint i=n;i>=1;--i)sa[t[x[i]]--]=i;
	for(rint k=1;k<=n;k<<=1) {
		int num=0;
		for(rint i=n-k+1;i<=n;++i)y[++num]=i;
		for(rint i=1;i<=n;++i)if(sa[i]>k)y[++num]=sa[i]-k;
		for(rint i=1;i<=m;++i)t[i]=0;
		for(rint i=1;i<=n;++i)++t[x[i]];
		for(rint i=1;i<=m;++i)t[i]+=t[i-1];
		for(rint i=n;i>=1;--i)sa[t[x[y[i]]]--]=y[i];
		swap(x,y),x[sa[1]]=1,num=1;
		for(rint i=2;i<=n;++i)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(num==n)break;m=num;
	}
}
void get_Height() {
	for(rint i=1;i<=n;++i)rk[sa[i]]=i;
	int k=0;
	for(rint i=1;i<=n;++i) {
		if(rk[i]==1)continue;
		if(k)--k;
		int j=sa[rk[i]-1];
		while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
		height[rk[i]]=k;
	}
}
signed main() {
	scanf("%s",s+1);
	n=strlen(s+1);
	get_SA();
	get_Height();
	for(rint i=1;i<=n;++i) {
		while(top&&height[st[top]]>=height[i])rp[st[top--]]=i-1;
		lp[i]=st[top]+1,st[++top]=i;
	}
	while(top)rp[st[top--]]=n;
	for(rint i=1;i<=n;++i)ans[height[i]]=max(ans[height[i]],rp[i]-lp[i]+2);
	ans[n+1]=1;for(rint i=n;i>=1;--i)ans[i]=max(ans[i],ans[i+1]);
	for(rint i=1;i<=n;++i)printf("%d\n",ans[i]);
	return 0;
}

m改成122,t数组(桶)开到N,就能过,不知道为啥

又试了一次,m=30 , t开40也RE

2020/5/19 19:57
加载中...