Description
农夫约翰发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。
约翰的牛奶按质量可以被赋予一个0到1000000之间的数。并且约翰记录了N（1＜=N＜=20000）天的牛奶质量值。他想知道最长的出现了至少K（2＜=K＜=N）次的模板的长度。比如1,2,3,2,3,2,3,1中2,3,2,3出现了两次。当K=2时，这个长度为4.
Input
第1行输入两个整数N和K。接下来N行每行一个整数表示当天的产奶质量。
Output
一个整数：N天中最长的出现了至少K次的模式的长度。
Sample Input
8 2
1
2
3
2
3
2
3
1
Sample Output
4
题解：
二分答案，直接在high里面check即可
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=;
int n,k,F;
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=(str<<)+(str<<)+ch-,ch=getchar();
return str;
}
int s[N],tmp[N],rk[N],sa[N],high[N];
bool comp(int i,int j){
if(rk[i]!=rk[j])return rk[i]<rk[j];
int ri=i+k<=n?rk[i+k]:-;
int rj=j+k<=n?rk[j+k]:-;
return ri<rj;
}
void Getsa(){
for(int i=;i<=n;i++)sa[i]=i,rk[i]=s[i];
for(k=;k<=n;k<<=){
sort(sa+,sa+n+,comp);
for(int i=;i<=n;i++)tmp[sa[i]]=tmp[sa[i-]]+comp(sa[i-],sa[i]);
for(int i=;i<=n;i++)rk[i]=tmp[i];
}
}
void Gethight(){
int h=,j;
for(int i=;i<=n;i++){
j=sa[rk[i]-];
if(h)h--;
for(;i+h<=n && j+h<=n;h++)if(s[i+h]!=s[j+h])break;
high[rk[i]-]=h;
}
}
bool check(int lim){
int tot=;
for(int i=;i<n;i++){
if(high[i]>=lim){
if(!tot)tot=;
else tot++;
}
else{
tot=;
}
if(tot>=F)return true;
}
return false;
}
int main()
{
n=gi();F=gi();
for(int i=;i<=n;i++)s[i]=gi();
Getsa();Gethight();
int l=,r=n,mid,ans;
while(l<=r){
mid=(l+r)>>;
if(check(mid))ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
return ;
}