XXVII.[BZOJ4310]跳蚤
我们仍然考虑二分子串。设当前二分的子串从位置\(pos\)开始，长度为\(len\)。考虑如何编写check函数。
一个naive的想法便是从前往后枚举所有极大的不存在小于二分串的子串的段，然后将该段数与规定段数作比较。
但是这有点问题——我们发现，这样做每次都是为段中所有后缀各添加一个字符，不好快速判断。但我们可以借鉴XIV.[SDOI2016]生成魔咒的思想，反过来倒序枚举极大段，这次每次都只是增加一个前缀了。
于是只要判断该前缀与二分串的字典序关系，如果字典序大于二分串就切一刀即可。
因为所有子串数是\(O(n^2)\)的，所以实际复杂度为\(O(n\log n^2)=O(n\times2\log n)=O(n\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
typedef long long ll;
ll sum[N];
int K;
namespace Suffix_Array{
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m,LG[N],mn[N][20];
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=ht[i];
for(int j=1;j<=LG[n-1];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]);
}
int LCP(int x,int y){
if(x==y)return n-x;
x=rk[x],y=rk[y];
if(x>y)swap(x,y);
x++;
int k=LG[y-x+1];
return min(mn[x][k],mn[y-(1<<k)+1][k]);
}
}
using namespace Suffix_Array;
bool che(ll ip){
int pos=lower_bound(sum,sum+n,ip)-sum,len=ip-sum[pos-1]+ht[pos];
pos=sa[pos];
// printf("%lld:%d,%d\n",ip,pos,len);
int k=0;
for(int i=n-1,j=n-1;i>=0;i=j,k++){//numerate backwards
for(;j>=0;j--){
int tmp=min({LCP(j,pos),i-j+1,len});//the minimum length possible
if(tmp==i-j+1&&tmp<=len)continue;//is ok
if(tmp==len)break;
if(rk[j]>rk[pos])break;//a greater lexicographicity, break.
}
if(i==j)return false;//there's a SINGLE CHARACTER that is lexicographically greater than substring checked, so break out.
}
return k<=K;
}
int main(){
scanf("%d%s",&K,s),n=strlen(s),m='z',SA();
// for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");
sum[0]=n-sa[0];
for(int i=1;i<n;i++)sum[i]=sum[i-1]+(n-sa[i])-ht[i];
// for(int i=0;i<n;i++)printf("%2d ",i);puts("");
// for(int i=0;i<n;i++)printf("%2d ",s[i]-'a');puts("");
// for(int i=0;i<n;i++)printf("%d ",sum[i]);puts("");
ll l=1,r=sum[n-1];
while(l<r){
ll mid=(l+r)>>1;
if(che(mid))r=mid;
else l=mid+1;
}
int pos=lower_bound(sum,sum+n,l)-sum,len=l-sum[pos-1]+ht[pos];
for(int i=0;i<len;i++)putchar(s[sa[pos]+i]);
return 0;
}
/*
3
ihgjhdgajhdjfjddddfdj
*/