【BZOJ4310】跳蚤

2016.03.22 19:53 Tue | 37次阅读 | 旧日oi | 固定链接 | 源码

题解

后缀数组+二分答案+贪心

先把后缀数组求出来,找出所有本质不同的回文串后二分答案。
如何验证一个答案呢?
考虑贪心,从后往前依次加入每个后缀,如果当前加入的后缀到上一个分割点这段子串的字典序<二分出来的那个串,那么这个点就需要断。

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define ll long long
int k,n,a[N];
char s[N];
int sa[2][N],rk[2][N],v[N],h[N],p,q;
ll sum[N];
int st,ed,len;
int mn[N][18],lg[N];
void mul(int k,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-1]+k]!=rk[SA[i]+k]);
}
void get_sa(int lim)
{
    p=1;
    for(int i=1;i<=n;i++) v[a[i]]++;
    for(int i=1;i<=lim;i++) v[i]+=v[i-1];
    for(int i=1;i<=n;i++) sa[p][v[a[i]]--]=i;
    for(int i=1;i<=n;i++) rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]);
    for(int k=1;k<=n;k<<=1,p^=1,q^=1) mul(k,sa[p],rk[p],sa[q],rk[q]);
    for(int k=0,j,i=1;i<=n;i++)
    {
        j=sa[p][rk[p][i]-1];
        while(a[j+k]==a[i+k]) k++;
        h[rk[p][i]]=k;if(k) k--;
    }
}
int get_mn(int l,int r)
{
    int t=lg[r-l+1];
    return min(mn[l][t],mn[r-(1<<t)+1][t]);
}
int lcp(int x,int y)
{
    if(x==y) return n-x+1;
    if(rk[p][x]>rk[p][y]) swap(x,y);
    return get_mn(rk[p][x]+1,rk[p][y]);
}
bool work(int l,int r)
{
    int x=min(lcp(l,st),min(r-l+1,len));
    if(x==r-l+1) return 1;
    if(x==len) return 0;
    return s[l+x]<=s[st+x];
}
bool check(ll mid)
{
    for(int i=1;i<=n;i++)
    if(sum[i]>=mid)
    {
        st=sa[p][i];
        len=mid-sum[i-1]+h[i];
        ed=st+len-1;
        break;
    }
    int ret=0;
    for(int j,i=n;i;i=j,ret++)
    {
        for(j=i;j;j--) if(!work(j,i)) break;
        if(j==i) return 0;
    }
    return ret<=k;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>k;
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1;
    get_sa(26);
    for(int i=1;i<=n;i++) mn[i][0]=h[i];
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i+(1<<j)-1<=n;i++)
        mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(n-sa[p][i]+1-h[i]);
    ll l=1,r=sum[n],mid;
    int ansl=1,ansr=n;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid)) ansl=st,ansr=ed,r=mid-1;
        else l=mid+1;
    }
    for(int i=ansl;i<=ansr;i++) printf("%c",s[i]);puts("");
}