正解:SA/最小表示法

解题报告:

传送门!

听说正解是最小表示法,,,O(n)然后常数还挺小的,,,

但是我不会QAQ!

所以先写下SA的做法趴,,,等get了最小表示法再来写正解QAQ

就这种题算是比较套路的,,,首先看到是个环,显然就考虑到倍增?

然后就跑个SA

然后从小往大扫sa数组,如果当前位置是<=序列长度n的,就直接输出然后return就好

注意一下的是n因为倍增了,所以长度要*2,这里建议是直接*2然后在求完之后再/2,不然每次都要打n*2的很容易错,,,

over,放下代码就好QAQ

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=620000+10;
int n,t[N<<1],sa[N<<1],ch[N<<1],str[N<<1],y[N<<1],x[N<<1];

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
il bool cmp(ri gd,ri gs,ri k){return y[gd]==y[gs] && y[gd+k]==y[gs+k];}
il void SA()
{
    ri m=n;
    rp(i,1,n)++t[x[i]=str[i]];
    rp(i,1,m)t[i]+=t[i-1];
    my(i,n,1)sa[t[x[i]]--]=i;
    for(ri k=1;k<=n;k<<=1)
    {
        ri p=0;
        rp(i,1,n)y[i]=0;rp(i,0,m)t[i]=0;
        rp(i,n-k+1,n)y[++p]=i;rp(i,1,n)if(sa[i]>k)y[++p]=sa[i]-k;
        rp(i,1,n)++t[x[y[i]]];
        rp(i,1,m)t[i]+=t[i-1];
        my(i,n,1)sa[t[x[y[i]]]--]=y[i];
        swap(x,y);
        x[sa[1]]=p=1;
        rp(i,2,n)x[sa[i]]=cmp(sa[i],sa[i-1],k)?p:++p;
        if(p>=n)break;m=p;
    }
}

int main()
{
//    freopen(".in","r",stdin);freopen(".out","w",stdout);
    n=read();rp(i,1,n)str[i]=str[i+n]=read();n<<=1;SA();//rp(i,1,n)if((sa[i]<<1)<=n)printf("%c",str[sa[i]+n-1]);
    rp(i,1,n)
        if((sa[i]<<1)<=n)
        {
            rp(j,0,(n>>1)-1)printf("%d ",str[sa[i]+j]);return 0;
        }    
    return 0;
}

放下代码QwQ