1717: [Usaco2006 Dec]Milk Patterns 产奶的模式

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 662  Solved: 372

[][][]

Description

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。

Input

* Line 1: 两个整数 N,K。

* Lines 2..N+1: 每行一个整数表示当天的质量值。

Output

* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度

Sample Input

8 2

1

2

3

2

3

2

3

1

Sample Output

4

HINT

 

Source

 

题解见后缀数组模板 可重叠的k次最长重复子串

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define N 20005 8 using namespace std; 9 int map[1000005];10 int sa[N],cc[N],rank[N],height[N],t1[N],t2[N],a[N],s[N];11 int len,cnt,k;12 inline int read()13 {14 int a=0,f=1; char c=getchar();15 while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar();}16 while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}17 return a*f;18 }19 inline bool cmp(int *y,int a,int b,int k)20 {21 int arank1=y[a];22 int brank1=y[b];23 int arank2=a+k>=len?-1:y[a+k];24 int brank2=b+k>=len?-1:y[b+k];25 return arank1==brank1&&arank2==brank2;26 }27 inline void make_sa()28 {29 int *x=t1,*y=t2;30 int m=256;31 for (int i=0;i
            
             =0;i--) sa[--cc[x[i]]]=i;35 for (int k=1;k
             
              <<=1)36 {37 int p=0;38 for (int i=len-k;i
              
               =k) y[p++]=sa[i]-k;41 for (int i=0;i
               
                =0;i--) sa[--cc[x[y[i]]]]=y[i];45 swap(x,y);46 m=1; x[sa[0]]=0;47 for (int i=1;i
                
                 =len) break;50 }51 }52 inline void make_height()53 {54 for (int i=0;i
                 
                  =k) return 1;74 }75 return 0;76 }77 int main()78 {79 len=read(); k=read();80 for (int i=0;i
                  
                   >1;92 if (judge(mid)) l=mid+1; else r=mid-1;93 }94 printf("%d",r);95 return 0;96 }