【BZOJ-4310】跳蚤 后缀数组 + ST表 + 二分

时间：2023-03-08 15:43:44

4310: 跳蚤

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit:
180  Solved: 83
[Submit][Status][Discuss]

Description

很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。
首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k
个子串中选择字典序最大的那一个。他称其为“魔力串”。
现在他想找一个最优的分法让“魔力串”字典序最小。

Input

第一行一个整数 k。
接下来一个长度不超过 105 的字符串

Output

输出一行，表示字典序最小的“魔力串”。

Sample Input

13
bcbcbacbbbbbabbacbcbacbbababaabbbaabacacbbbccaccbcaabcacbacbcabaacbccbbcbcbacccbcccbbcaacabacaaaaaba

Sample Output

cbc

HINT

S的长度<=100000

Source

Solution

首先求出后缀数组和height数组，这样能得到本质不同的子串数目

这里利用：本质不同的子串$=\sum(Len-SA[i]-height[i])$利用SA[],height[]的定义很好想

然后要求最大值最小，显然二分，二分一个mid，求出第mid大的子串

然后贪心的检验，从后往前扫，当字典序超过二分的值时，划分一下，看划分个数与K的关系即可

中间涉及比较，用LCP实现即可，显然ST表非常方便

Code

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define maxn 1000100

char S[maxn]; int SA[maxn],len,K;

int wa[maxn],wb[maxn],ws[maxn],wv[maxn];

long long tot;

int L,R;

inline int cmp(int *r,int a,int b,int l)

{

    return r[a]==r[b]&&r[a+l]==r[b+l];

}

inline void DA(char *r,int *sa,int n,int m)

{

    int p,*x=wa,*y=wb,*t;

    for (int i=; i<m; i++) ws[i]=;

    for (int i=; i<n; i++) ws[x[i]=r[i]]++;

    for (int i=; i<m; i++) ws[i]+=ws[i-];

    for (int i=n-; i>=; i--) sa[--ws[x[i]]]=i;

    p=; for (int j=; p<n; j*=,m=p)

        {

            p=; for (int i=n-j; i<n; i++) y[p++]=i;

            for (int i=; i<n; i++) if (sa[i]>=j) y[p++]=sa[i]-j;

            for (int i=; i<n; i++) wv[i]=x[y[i]];

            for (int i=; i<m; i++) ws[i]=;

            for (int i=; i<n; i++) ws[wv[i]]++;

            for (int i=; i<m; i++) ws[i]+=ws[i-];

            for (int i=n-; i>=; i--) sa[--ws[wv[i]]]=y[i];

            t=x,x=y,y=t;p=;x[sa[]]=;

            for (int i=; i<n; i++)

                x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

        }

}

int rank[maxn],height[maxn];

inline void calheight(char *r,int *sa,int n)

{

    int k=;

    for (int i=; i<=n; i++) rank[sa[i]]=i;

    for (int i=; i<n; height[rank[i++]]=k)

        {k?k--:;for (int j=sa[rank[i]-]; r[i+k]==r[j+k]; k++);}

}

int log2[maxn]; int dp[maxn][];

void ST(int n)

{

    log2[]=-;

    for (int i=; i<=n; i++)

        if (i&(i-)) log2[i]=log2[i-];

            else log2[i]=log2[i-]+;

    for (int i=; i<=n; i++) dp[i][]=height[i];

    for (int j=; (<<j)<=len; j++)

        for (int i=; i+(<<j)-<=n; i++)

            dp[i][j]=min(dp[i][j-],dp[i+(<<(j-))][j-]);

}

int RMQ(int l,int r)

{

    int tmp=log2[r-l+];

    return min(dp[l][tmp],dp[r-(<<tmp)+][tmp]);

}

int LCP(int l,int r)

{

    if (l==r) return len-l;

    l=rank[l]; r=rank[r];

    if (l>r) swap(l,r); l++;

    return RMQ(l,r);

}

void Get(long long k)

{

    for (int i=; i<=len; i++)

        if ((long long)(len-SA[i]-height[i])<k) k-=(long long)(len-SA[i]-height[i]);

            else {L=SA[i],R=SA[i]+height[i]+k-; break;}

}

bool Compare(int l1,int r1,int l2,int r2)

{

    int len1=r1-l1+,len2=r2-l2+,lcp=LCP(l1,l2);

    if (len1<=len2 && lcp>=len1) return ;

    if (len1>len2 && lcp>=len2) return ;

    if (lcp>=len1 && lcp>=len2) return len1>len2? :;

    return S[l1+lcp]>S[l2+lcp]? :;

}

int Check()

{

    int cnt=,last=len-;

    for (int i=len-; i>=; i--)

        {

            if (S[i]>S[L]) return ;

            if (!Compare(i,last,L,R)) ++cnt,last=i;

            if (cnt>K) return ;

        }

    return ;

}

int main()

{

    scanf("%d",&K); scanf("%s",S);

    len=strlen(S); S[len]=;

    DA(S,SA,len+,); calheight(S,SA,len);

    ST(len);

    for (int i=; i<=len; i++) tot+=len-SA[i]-height[i];

//    printf("%d\n",tot);

    long long l=,r=tot;

    while (l<=r)

        {

            long long mid=(l+r)>>;

            Get(mid);

//          printf("L=%d R=%d\n",L,R);

            if (Check()) r=mid-; else l=mid+;

//          printf("%I64d %I64d\n",l,r);

        }

    Get(r+);

    for (int i=L; i<=R; i++) putchar(S[i]);

    return ;

}

相关文章