后缀数组，还是对height数据进行分组。然后二分答案。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <map> 5 using namespace std; 6 const int maxn=20000+10; 7 int num[maxn]; 8 int sa[maxn],t[maxn],t2[maxn],c[maxn],height[maxn],rank[maxn]; 9 map<int,int> a; 10 int n,K; 11 void build_sa(int m,int n,int *s) 12 { 13 int i,*x=t,*y=t2; 14 for(i=1;i<m;i++) c[i]=0; 15 for(i=0;i<n;i++) c[x[i]=a[s[i]]]++; 16 for(i=2;i<m;i++) c[i]+=c[i-1]; 17 for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i; 18 for(int k=1;k<=n;k<<=1) 19 { 20 int p=0; 21 for(i=n-k;i<n;i++) y[p++]=i; 22 for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; 23 for(i=1;i<m;i++) c[i]=0; 24 for(i=0;i<n;i++) c[x[y[i]]]++; 25 for(i=2;i<m;i++) c[i]+=c[i-1]; 26 for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; 27 swap(x,y); 28 p=2;x[sa[0]]=1; 29 for(i=1;i<n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++; 30 if(p>n) break; 31 m=p; 32 } 33 } 34 void getHeight(int n) 35 { 36 int i,j,k=0; 37 for(i=0;i<n;i++) rank[sa[i]]=i; 38 for(i=0;i<n;i++) 39 { 40 if(k) k--; 41 if(rank[i]) 42 { 43 int j=sa[rank[i]-1]; 44 while(num[i+k]==num[j+k]) k++; 45 height[rank[i]]=k; 46 } 47 } 48 } 49 int bsearch(int n) 50 { 51 int low=3,high=n+1,mid,i,cou; 52 int flag; 53 while(high>low) 54 { 55 flag=0; 56 cou=1; 57 mid=low+(high-low)/2; 58 for(i=1;i<n;i++) 59 { 60 if(height[i]>=mid) cou++; 61 else 62 { 63 if(cou>=K) 64 { 65 flag=1; 66 break; 67 } 68 cou=1; 69 } 70 } 71 if(cou>=K) flag=1; 72 if(flag) low=mid+1; 73 else high=mid; 74 } 75 return low-1; 76 } 77 int main() 78 { 79 //freopen("1.txt","r",stdin); 80 scanf("%d%d",&n,&K); 81 int i,tem,tot=1; 82 for(i=0;i<n;i++) 83 { 84 scanf("%d",&num[i]); 85 if(!a[num[i]]) a[num[i]]=tot++; 86 } 87 build_sa(tot,n,num); 88 getHeight(n); 89 int ans=bsearch(n); 90 printf("%d\n",ans); 91 return 0; 92 } 93