[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即可

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 const int N=20005;
 9 int n,k,F;
10 int gi(){
11     int str=0;char ch=getchar();
12     while(ch>'9' || ch<'0')ch=getchar();
13     while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
14     return str;
15 }
16 int s[N],tmp[N],rk[N],sa[N],high[N];
17 bool comp(int i,int j){
18     if(rk[i]!=rk[j])return rk[i]<rk[j];
19     int ri=i+k<=n?rk[i+k]:-1;
20     int rj=j+k<=n?rk[j+k]:-1;
21     return ri<rj;
22 }
23 void Getsa(){
24     for(int i=1;i<=n;i++)sa[i]=i,rk[i]=s[i];
25     for(k=1;k<=n;k<<=1){
26         sort(sa+1,sa+n+1,comp);
27         for(int i=1;i<=n;i++)tmp[sa[i]]=tmp[sa[i-1]]+comp(sa[i-1],sa[i]);
28         for(int i=1;i<=n;i++)rk[i]=tmp[i];
29     }
30 }
31 void Gethight(){
32     int h=0,j;
33     for(int i=1;i<=n;i++){
34         j=sa[rk[i]-1];
35         if(h)h--;
36         for(;i+h<=n && j+h<=n;h++)if(s[i+h]!=s[j+h])break;
37         high[rk[i]-1]=h;
38     }
39 }
40 bool check(int lim){
41     int tot=0;
42     for(int i=1;i<n;i++){
43         if(high[i]>=lim){
44             if(!tot)tot=2;
45             else tot++;
46         }
47         else{
48             tot=0;
49         }
50         if(tot>=F)return true;
51     }
52     return false;
53 }
54 int main()
55 {
56     n=gi();F=gi();
57     for(int i=1;i<=n;i++)s[i]=gi();
58     Getsa();Gethight();
59     int l=0,r=n,mid,ans;
60     while(l<=r){
61         mid=(l+r)>>1;
62          if(check(mid))ans=mid,l=mid+1;
63         else r=mid-1;
64     }
65     printf("%d
",ans);
66     return 0;
67 }