二分+后缀数组
对于height分块然后二分判定就可以了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=20005;
int sa[N],rank[N],rank2[N],n,height[N],wa[N],ws[N],a[N],k;
bool cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}
void GetSA(int *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--){sa[--ws[x[i]]]=i;}
for(j=p=1;p<n;j*=2,m=p){
for(p=0,i=n-j;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];
for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void CalHeight(int *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k){
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
}
bool Check(int x){
int cnt,i=2;
while(1){
while(i<=n && height[i]<x)i++;
if(i>n)break;
cnt=1;
while(i<=n && height[i]>=x){cnt++;i++;}
if(cnt>=k)return 1;
}
return 0;
}
int Div2(){
int l=1,r=n,ans=1;
while(l<=r){
int mid=l+r>>1;
if(Check(mid)){ans=mid;l=mid+1;}
else r=mid-1;
}
return ans;
}
int main(){
freopen("1717.in","r",stdin);
freopen("1717.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
a[n]=0;
GetSA(a,sa,n+1,N-4);
CalHeight(a,sa,n);
printf("%d\n",Div2());
return 0;
}
评论 (0)
