1 #include "stdio.h" 2 #define maxn 20010 3  4 int wa[maxn],wb[maxn],wv[maxn],ws[maxn]; 5 int rank[maxn],height[maxn]; 6 int r[maxn],sa[maxn],ans[maxn]; 7 int n,res,k; 8  9 int cmp(int *r,int a,int b,int l)10 {11     return r[a]==r[b]&&r[a+l]==r[b+l];12 }13 14 void da(int *r,int *sa,int n,int m)15 {16     int i,j,p,*x=wa,*y=wb,*t;17     for(i=0; i<m; i++) ws[i]=0;18     for(i=0; i<n; i++) ws[x[i]=r[i]]++;19     for(i=1; i<m; i++) ws[i]+=ws[i-1];20     for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;21     for(j=1,p=1; p<n; j*=2,m=p)22     {23 24         for(p=0,i=n-j; i<n; i++) y[p++]=i;25         for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;26         for(i=0; i<n; i++) wv[i]=x[y[i]];27         for(i=0; i<m; i++) ws[i]=0;28         for(i=0; i<n; i++) ws[wv[i]]++;29         for(i=1; i<m; i++) ws[i]+=ws[i-1];30         for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];31         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)32             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;33     }34     return;35 }36 37 void calheight(int *r,int *sa,int n)38 {39     int i,j,k=0;40     for(i=1; i<=n; i++) rank[sa[i]]=i;41     for(i=0; i<n; height[rank[i++]]=k)42         for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);43     return;44 }45 46 bool calc(int x)        //x:length47 {48     int rec[maxn];49     int nm=0;50     for (int i=1;i<=n;i++)51     {52         if (height[i]<x)53         {54             nm++;55             rec[nm]=i;56         }57     }58     nm++;   rec[nm]=n+1;59     for (int i=1;i<=nm;i++)60     {61         int tl=rec[i-1],tr=rec[i];62         if (tr-tl>=k)      return true;63     }64     return false;65 }66 67 int main()68 {69     scanf("%d %d",&n,&k);70     for (int i=0; i<n; i++)71         scanf("%d",&r[i]);72     r[n]=0;73 74     da(r,sa,n+1,200);75     calheight(r,sa,n);76 77     //TODO: Please Code Here78     int l=0,r=n,res=0;79     while (r>=l)80     {81         int mid=(l+r)/2;82         if (calc(mid))83         {84             if (mid>res)    res=mid;85             l=mid+1;86         }87         else88             r=mid-1;89     }90     printf("%d\n",res);91     return 0;92 }