1 /* 2 求可重叠的至少重复K次的最长字串 3 以1为下标起点，因为a[i]最大到1000000，所以要先离散一下 4 二分长度len 5 然后O(n)检验 6 后看h[i]是否有连续的一段h[i]大于len的，并且h[i]连续的长度大于K则满足  7 */ 8 #include<stdio.h> 9 #include<string.h>10 #include<algorithm>11 using namespace std;12 const int maxn = 20010;13 int c[maxn],sa[maxn],t1[maxn],t2[maxn],n,m,K,tot,t[maxn],num[maxn],a[maxn],rank[maxn],height[maxn];14 15 bool cmp(int *r, int a, int b, int l){16     return r[a]==r[b] && r[a+l]==r[b+l];17 }18 19 void suffix(int *a, int n, int m){20     int p=0, *x=t1, *y=t2;21     for (int i=0; i<=m; i++) c[i]=0;22     for (int i=1; i<=n; i++) c[x[i]=a[i]]++;23     for (int i=1; i<=m; i++) c[i]+=c[i-1];24     for (int i=n; i>=1; i--) sa[c[x[i]]--]=i;25     for (int j=1; j<=n; j<<=1){26         p=0;27         for (int i=n-j+1; i<=n; i++) y[++p]=i;28         for (int i=1; i<=n; i++) if (sa[i]>j) y[++p]=sa[i]-j;29         for (int i=0; i<=m; i++) c[i]=0;30         for (int i=1; i<=n; i++) c[x[y[i]]]++;31         for (int i=1; i<=m; i++) c[i]+=c[i-1];32         for (int i=n; i>=1; i--) sa[c[x[y[i]]]--]=y[i];33         swap(x,y); x[sa[1]]=1; p=1;34         for (int i=2; i<=n; i++)35             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p:++p;36         m=p; if (p>=n) break;37     }38     //for (int i=1; i<=n; i++) printf("%d\n", sa[i]);39 }40 41 void get_height(int *a){42     int k=0,j;43     for (int i=1; i<=n; i++) rank[sa[i]]=i;44     for (int i=1; i<=n; i++){45         j=sa[rank[i]-1];46         k?k--:0;47         while (a[j+k]==a[i+k]) k++;48         height[rank[i]]=k;49     }50     //for (int i=1; i<=n; i++) printf("%d\n", height[i]);51 }52 53 int find(int x){54     int l=1, r=tot, ans;55     while (l<=r){56         int mid=l+r>>1;57         if (t[mid]<=x) ans=mid,l=mid+1;58         else r=mid-1;59     }60     return ans;61 }62 63 bool check(int k){64     int i,tot=0;65     for (i=1; i<=n; i++){66         if (height[i]>=k) tot++;67         else{68             if (tot+1>=K) return 1;69             else tot=0;70         }71     }72     if (tot+1>=K) return 1; return 0;73 }74 75 int main(){76     scanf("%d%d", &n, &K);77     for (int i=1; i<=n; i++) scanf("%d", &a[i]),num[i]=a[i];78     sort(num+1,num+1+n); tot=0;79     t[++tot]=num[1];80     for (int i=2; i<=n; i++)81         if (num[i]!=num[i-1])82             t[++tot]=num[i];83     for (int i=1; i<=n; i++) a[i]=find(a[i]);84     suffix(a,n,n);85     get_height(a);86     int l=1,r=n,ans;87     while (l<=r){88         int mid=l+r>>1;89         if (check(mid)) ans=mid,l=mid+1;90         else r=mid-1;91     }92     printf("%d\n", ans);93     return 0;94 }