又双叒叕是一道后缀数组
这次不像之前那么难了~~然而还是不会~~
题意：求出现至少k次的最长子串的长度
我们先求出这个序列的het值
然后二分答案
check的时候，把后缀分成若干组
判断有没有一组的后缀数>=k
有则答案可行，否则就从当前这一个后缀重新开始计数
与省选题相比，还是略简单一些
```cpp
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=2e4+5;
int n,m,a[N];
struct SA
{
int u,sa[N],rank[N],top[N],tax[N],het[N];
inline void qsort()
{
memset(tax,0,sizeof(tax));
for (reg int i=1;i<=n;i++) ++tax[rank[i]];
for (reg int i=1;i<=u;i++) tax[i]+=tax[i-1];
for (reg int i=n;i>=1;i--)
sa[tax[rank[top[i]]]--]=top[i];
}
inline void getSA()
{
for (reg int i=1;i<=n;i++)
rank[i]=a[i],top[i]=i;
u=127; qsort();
for (reg int w=1,p=0;p<n;u=p,w<<=1)
{
p=0;
for (reg int i=1;i<=w;i++) top[++p]=n-w+i;
for (reg int i=1;i<=n;i++)
if (sa[i]>w) top[++p]=sa[i]-w;
qsort(); swap(rank,top);
rank[sa[1]]=p=1;
for (reg int i=2;i<=n;i++)
if (top[sa[i-1]]==top[sa[i]]&&top[sa[i-1]+w]==top[sa[i]+w])
rank[sa[i]]=p;
else rank[sa[i]]=++p;
}
int k=0;
for (reg int i=1;i<=n;i++)
{
k=(k?k-1:0);
while (a[i+k]==a[sa[rank[i]-1]+k]) ++k;
het[rank[i]]=k;
}
}
}R;
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline bool check(int k)
{
int l=1,r=1;
for (reg int i=2;i<=n+1;i++)
if (R.het[i]>=k) ++r;
else if (r-l+1>=m) return 1;
else l=r=i;
return 0;
}
inline int getans()
{
int l=0,r=n,ans=0;
while (l<=r)
{
int mid=(l+r)>>1;
if (check(mid))
{
ans=mid; l=mid+1;
}
else r=mid-1;
}
return ans;
}
int main()
{
n=read(),m=read();
for (reg int i=1;i<=n;a[i++]=read());
R.getSA();
printf("%d\n",getans());
return 0;
}
```