后缀数组一·重复旋律

时间限制:5000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。

小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。旋律是一段连续的数列，相似的旋律在原数列可重叠。比如在1 2 3 2 3 2 1 中 2 3 2 出现了两次。

小Hi想知道一段旋律中出现次数至少为K次的旋律最长是多少？

输入

第一行两个整数 N和K。1≤N≤20000 1≤K≤N

接下来有 N 个整数，表示每个音的数字。1≤数字≤100

输出

一行一个整数，表示答案。

样例输入

8 212323231

样例输出

4

 

 

 

二分答案，判断height数组的值有没有连续m-1个大于等于mid的

1 #include
      
        2 using namespace std; 3 typedef long long ll; 4 #define maxn 1000006 5  6 struct DA{ 7     int wa[maxn],wb[maxn],wv[maxn],ws[maxn]; 8     int cmp(int *r,int a,int b,int l){ 9         return r[a]==r[b]&&r[a+l]==r[b+l];10     }11 12     void da(int *r,int *sa,int n,int m){13         int i,j,p,*x=wa,*y=wb,*t;14         for(i=0;i
       
        =0;i--) sa[--ws[x[i]]]=i;18 19         for(j=1,p=1;p
        
         =j) y[p++]=sa[i]-j;23             for(i=0;i
         
          =0;i--) sa[--ws[wv[i]]]=y[i];29 30             for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i
          
           =mid){53             co++;54             if(co>=m) return true;55         }56         else{57             co=1;58         }59     }60     return false;61 }62 63 int main(){64     #ifndef ONLINE_JUDGE65         freopen("input.txt","r",stdin);66     #endif67     std::ios::sync_with_stdio(false);68     cin>>n>>m;69     for(int i=0;i
           
            >a[i];70 da.da(a,b,n+1,1005);71 da.calheight(a,b,n);72 int l=0,r=n,mid,tmp;73 int ans=0;74 while(l<=r){75 mid=l+r>>1;76 if(erfen(mid))l=mid+1;77 else r=mid-1;78 }79 cout<
            
             <