越毒瘤越好,自然写出,不用刻意压行。
不开符号匹配的自然码风镇楼:
const I N=1e5+10;
I h[N],a[N],sa[N],p,n,m,rk[N],ork[N],c[N],id[N];LL s;
void gsa(){memset(c+1,0,m*4);
for(I i=n;i;--i)++c[rk[i]],ork[i]=rk[i];
for(I i=1;i<=m;++i)c[i]+=c[i-1];
for(I i=n;i;--i)sa[c[rk[id[i]]]--]=id[i];}
bool eq(I x,I y,I k){return ork[x]==ork[y]&&ork[x+k]==ork[y+k];}
void grk(){for(I i=1;i<=n;++i)id[i]=i,rk[i]=a[i];gsa();
for(I k=1,i;;k<<=1,m=p){for(p=0,i=n;i>n-k;--i)id[++p]=i;
for(i=1;i<=n;++i)if(sa[i]>k)id[++p]=sa[i]-k;
gsa();for(p=0,i=1;i<=n;++i)rk[sa[i]]=eq(sa[i],sa[i-1],k)?p:++p;
if(p==n){for(i=1;i<=n;++i)sa[rk[i]]=i;break;}}}