[USACO Dec06]产奶的模式

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

题解：

二分答案，直接在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 ;

 }

秒客网