[bzoj4310]跳蚤

来自FallDream的博客，未经允许，请勿转载，谢谢。

很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。

首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。

现在他想找一个最优的分法让“魔力串”字典序最小。

|S|<=10^5

考虑后缀数组求出所有子串，然后二分答案是哪一个子串，从后往前判断，需要切就切开即可。

求出height之后，不同的子串个数是$sum{n-sa[i]-Height[i]+1}$ 这个比较好理解。找第k大的时候从小到大计算即可。

然后判断可以借用lcp，用st表来查询即可

复杂度nlogn

#include<iostream>
#include<cstdio>
#include<cstring>
#define MN 100000
#define MD 17
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
long long tot=0;
int K,n,sa[2][MN+5],rk[2][MN+5],v[MN+5],k,Log[MN+5],F[MD+1][MN+5],p=1,L,R,q=0,H[MN+5];
char st[MN*2+5];

void CalSa(int*SA,int*RK,int*sa,int*rk)
{
    for(int i=1;i<=n;++i) v[rk[sa[i]]]=i;
    for(int i=n;i;--i)
        if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k;
    for(int i=n-k+1;i<=n;++i) SA[v[rk[i]]--]=i;
    for(int i=1;i<=n;++i)
        RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
}

void GetH(int*sa,int*rk)
{
    for(int i=1,k=0;i<=n;H[rk[i++]]=k,k?--k:0) if(rk[i]>1)
        for(int j=sa[rk[i]-1];st[i+k]==st[j+k];++k);
}

int Query(int l,int r)
{
    int s=Log[r-l+1];
    return min(F[s][l],F[s][r-(1<<s)+1]);
}

bool Cmp(int l,int r,int L,int R)
{
    if(l==L){return r>R;}
    int rk1=rk[q][l],rk2=rk[q][L],lcp=Query(min(rk1,rk2)+1,max(rk1,rk2));
    if(lcp>=max(r-l+1,R-L+1)) return false;
    if(lcp>=min(r-l+1,R-L+1)) return (r-l>R-L);
    return st[l+lcp]>st[L+lcp];
}

int Check()
{
    int sum=0,Rt=n;
    for(int i=n;i;--i) if(Cmp(i,Rt,L,R)) Rt=i,++sum;
    return sum+1;
}

void GetKth(long long Rk)
{
    for(int i=1;i<=n;++i)
    {
        int num=n-sa[q][i]-H[i]+1;
        if(Rk>num) Rk-=num;
        else {R=(L=sa[q][i])+H[i]+Rk-1;return;}
    }
}

int main()
{
    K=read();scanf("%s",st+1);n=strlen(st+1);
    for(int i=1;i<=n;++i) ++v[st[i]-'a'];
    for(int i=1;i<=26;++i) v[i]+=v[i-1];
    for(int i=1;i<=n;++i) sa[q][v[st[i]-'a']--]=i;
    for(int i=1;i<=n;++i) rk[q][sa[q][i]]=rk[q][sa[q][i-1]]+(st[sa[q][i]]!=st[sa[q][i-1]]);
    for(k=1;k<n;k<<=1)
    {
        CalSa(sa[p],rk[p],sa[q],rk[q]);
        swap(p,q);
    }
    GetH(sa[q],rk[q]);Log[0]=-1;
    for(int i=1;i<=n;++i) Log[i]=Log[i>>1]+1;
    for(int i=1;i<=n;++i) F[0][i]=H[i];
    for(int i=1;i<=MD;++i)
        for(int j=1;j<=n;++j)
        {
            int l=j+(1<<i-1);
            F[i][j]=min(F[i-1][j],l<=n?F[i-1][l]:n);
        }
    for(int i=1;i<=n;++i) tot+=n-sa[q][i]+1-H[i];
    long long l=1,r=tot,mid,res;
    while(l<=r)
    {
        GetKth(mid=l+r>>1);
        if(Check()<=K) res=mid,r=mid-1;
        else l=mid+1;
    }
    GetKth(res);
    for(int i=L;i<=R;++i) printf("%c",st[i]);
    return 0;
}