LINK
此题的常规做法是 二分 + 后缀数组 ，但本蒟蒻还是习惯写 并查集 的做法
算法流程
1.离散化是肯定要有的，给的数据太大了，不离散化会RE
2.先跑一遍SA，把最重要的h数组求出来
3.把h从大到小排序，从大到小枚举重复串的长度，同时遍历h数组，若对于\(h_i\)有\(h_i\)大于等于当前枚举的长度，就把\(h_i\)所连接的两个节点合并（见下文），求出合并后的并查集的大小，最后再判断一下是否大于题目的要求的大小，若符合要求就输出当前枚举的长度，并结束程序。
整个算法的时间复杂度为\(O(n log_2 n)\)，主要性能瓶颈在于排序。
主要解释一下第三个步骤的用意
为什么说\(h_i\)连接了两个节点
首先对于数据 1 1 2 1 1，它的 SA 为 5 4 1 2 3，而\(h_i\)则可以看成连接\(i\)与\(i-1\)节点的桥梁
我们回归\(h\)数组的本质，它的意义为排名为\(i\)的后缀与排名为\(i-1\)的后缀的最长公共前缀，则我们可以把\(i\)和\(i-1\)看成两个节点，\(h_i\)就是连接这两个节点的无向边，其权值就为\(h_i\)本身的值
并查集大小的意义
若对于一个大小已经大于等于题目要求的个数的并查集，则说明这个并查集里所有点连接的所有边的值都大于等于当前枚举的值，也就是说这一段区间的所有后缀都有一个长度大于等于当前枚举的值的公共前缀，重复的前缀的个数就等于当前并查集的大小
Code：
#include<stdio.h>
#include<algorithm>
using namespace std;
#define rint register int
#define N 200007template<class T>
inline void read(T &x){x=0;char c=getchar();T flag=1;while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}x*=flag;
}struct Node{int val,pos;
}pre[N];
struct E{int val,to;
}h[N];
int n,m,lim,a[N];
int rk[N],tp[N],sa[N],cnt[N],fa[N],size[N];inline int find(int x){return (x==fa[x])? x:(fa[x]=find(fa[x]));}
inline bool Cmp1(const Node x,const Node y){return x.val<y.val;}
inline bool Cmp2(const E x,const E y){return x.val>y.val;}
inline void sort_(){for(rint i=0;i<=m;i++) cnt[i]=0;for(rint i=1;i<=n;i++) cnt[rk[i]]++;for(rint i=0;i<=m;i++) cnt[i]+=cnt[i-1];for(rint i=n;i>=1;i--)sa[cnt[rk[tp[i]]]--]=tp[i];
}
inline void SA(){for(rint i=1;i<=n;i++) tp[i]=i,rk[i]=a[i];sort_();for(rint w=1,p=0;p<n;m=p,w<<=1){p=0;for(rint i=n-w+1;i<=n;i++) tp[++p]=i;for(rint i=1;i<=n;i++)if(sa[i]>w) tp[++p]=sa[i]-w;sort_();swap(rk,tp);rk[sa[1]]=p=1;for(rint i=2;i<=n;i++)rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])? p:++p;}
}
int main(){read(n);read(lim);for(rint i=1;i<=n;i++) read(a[i]),pre[i]=(Node){a[i],i};sort(pre+1,pre+1+n,Cmp1);for(rint i=1;i<=n;i++)a[pre[i].pos]=(pre[i].val==pre[i-1].val)? m:(++m);
/* for(rint i=1;i<=n;i++) printf("%d ",a[i]);*/SA();
/* for(rint i=1;i<=n;i++) printf("%d ",sa[i]);printf("\n");*/int h_=0;for(rint i=1;i<=n;i++){rint t=sa[rk[i]-1];while(a[t+h_]==a[i+h_]) h_++;h[rk[i]].val=h_,h[i].to=i;h_=max(0,h_-1);size[i]=1,fa[i]=i;}sort(h+1,h+1+n,Cmp2);for(int i=n,j=0;i>=0;i--){while(h[j+1].val>=i){rint u=h[++j].to,v=u-1;u=find(u),v=find(v);fa[v]=u;size[u]+=size[v];if(size[u]>=lim){printf("%d",i);return 0;}}}
}
