题目链接

题意分析

给你一个字符串 让你求\(1-n\)长度下的字符串的中字典序最小并且最靠左的字符串的开头位置

我们考虑先建出\(SA\)

然后考虑对于一个字符串后缀排序之后

baba

后缀排序之后 先不管位置 只关心字典序

数字代表当前更新长度

a 1  
aba 2 3
ba 
baba 4

我们可以发现 第二个后缀还可以更新长度为\(1\)的子串

所以我们考虑使用二分 求刚好可以满足的位置

然后我们再使用\(RMQ\)求这些位置中对应原串位置最靠左的位置

然后更新即可

CODE:

/*-------------OI使我快乐-------------*/
char s[M];
int n,key,have;int num[M],res[M],ans[M];
int ST[M][20][2],lg[M];
int SA[M],rnk[M],cdy[M],wzy[M],vis[M],hei[M];
IL void Rsort()
{
    for(R int i=0;i<=key;++i) vis[i]=0;
    for(R int i=1;i<=n;++i) vis[cdy[i]]++;
    for(R int i=1;i<=key;++i) vis[i]+=vis[i-1];
    for(R int i=n;i;--i) SA[vis[cdy[wzy[i]]]--]=wzy[i];
}
IL void get_SA()
{
    for(R int i=1;i<=n;++i) cdy[i]=num[i],wzy[i]=i;Rsort();
    for(R int x=1;x<=n;x<<=1)
    {
        int cnt=0;
        for(R int i=n-x+1;i<=n;++i) wzy[++cnt]=i;
        for(R int i=1;i<=n;++i) if(SA[i]>x) wzy[++cnt]=SA[i]-x;
        Rsort();swap(cdy,wzy);cdy[SA[cnt=1]]=1;
        for(R int i=2;i<=n;++i)
        cdy[SA[i]]=(wzy[SA[i]]==wzy[SA[i-1]]&&wzy[SA[i]+x]==wzy[SA[i-1]+x] ? cnt:++cnt);
        if(cnt==n) break;
        else key=cnt;
    }
}
IL void get_hei()
{
    for(R int i=1;i<=n;++i) rnk[SA[i]]=i;
    int lat,k=0;
    for(R int i=1;i<=n;++i)
    {
        if(k) --k;
        lat=SA[rnk[i]-1];
        while(num[lat+k]==num[i+k]) ++k;
        hei[rnk[i]]=k;
    }
}
IL void pre()
{
    for(R int i=1;(1<<i)<=300000;++i) lg[1<<i]=i;
    for(R int i=2;i<=300000;++i) if(!lg[i]) lg[i]=lg[i-1];
    for(R int i=1;i<=n;++i) ST[i][0][0]=hei[i];
    for(R int j=1;(1<<j)<=n;++j)
     for(R int i=1;i<=n;++i)
      ST[i][j][0]=min(ST[i][j-1][0],ST[i+(1<<(j-1))][j-1][0]);
    for(R int i=1;i<=n;++i) ST[i][0][1]=SA[i];
    for(R int j=1;(1<<j)<=n;++j)
     for(R int i=1;i<=n;++i)
      ST[i][j][1]=min(ST[i][j-1][1],ST[i+(1<<(j-1))][j-1][1]);  
}
IL int qury_hei(int le,int ri)
{
    if(le>ri) swap(le,ri);++le;int lx=lg[ri-le+1];
    return min(ST[le][lx][0],ST[ri-(1<<lx)+1][lx][0]);
}
IL int qury_min(int le,int ri)
{
    if(le>ri) swap(le,ri);int lx=lg[ri-le+1];
    return min(ST[le][lx][1],ST[ri-(1<<lx)+1][lx][1]);
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(have);read(n);
    if(have==26)
    {
        scanf("%s",s+1);key=130;
        for(R int i=1;i<=n;++i) num[i]=s[i]-'0'+1;
    }
    else
    {
        for(R int i=1;i<=n;++i) read(num[i]),res[i]=num[i];
        sort(res+1,res+n+1);key=unique(res+1,res+n+1)-res-1;
        for(R int i=1;i<=n;++i) num[i]=lower_bound(res+1,res+key+1,num[i])-res;
//      for(R int i=1;i<=n;++i)
//      printf("%d%c",num[i],(i==n ? '\n':' '));
//      printf("key %d\n",key);
    }
    get_SA();get_hei();pre();
//  printf("SA : ");for(R int i=1;i<=n;++i) printf("%d%c",SA[i],(i==n ? '\n':' '));
//  printf("height : ");for(R int i=1;i<=n;++i) printf("%d%c",hei[i],(i==n ? '\n':' '));    
    for(R int i=1,tail=1;i<=n;++i)
    {
        while(tail<n&&n-SA[tail]+1<i) ++tail;
//维护单调指针   
        ans[i]=SA[tail];
        int le=tail+1,ri=n,can=-1;
        while(le<=ri)
        {
            int mid=(le+ri)>>1;
            if(qury_hei(tail,mid)>=i) can=mid,le=mid+1;
            else ri=mid-1; 
        }
//二分那个位置 用lcp判断是否可以满足贡献出那个串        
        if(can!=-1) ans[i]=min(ans[i],qury_min(tail,can));
//存在的话 我们就用中间最左端的位置更新        
    }
    for(R int i=1;i<=n;++i) printf("%d%c",ans[i],(i==n ? '\n':' '));
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

HEOI 2019 RP++

P5108 仰望半月的夜空

原文：https://www.cnblogs.com/LovToLZX/p/10590524.html