谔谔我,写了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