注意：对整型数组求sa时，s[n]请置成-1。

请离散化。

可重叠的 k 次最长重复子串（pku3261）

给定一个字符串，求至少出现 k 次的最长重复子串，这 k 个子串可以重叠。

算法分析：

先二分答案，然后将后缀分成若干组。 不

同的是，这里要判断的是有没有一个组的后缀个数不小于 k。如果有，那么存在

k 个相同的子串满足条件，否则不存在。这个做法的时间复杂度为 O(nlogn)。

#include
     
      #include
      
       #include
       
        using namespace std;#define N 20001struct Point{int p,v;}T[N];bool operator < (Point a,Point b){return a.v
        
         =n?-1:y[sa[i-1]+k])==(sa[i]+k>=n?-1:y[sa[i]+k])));}void build_sa(int range){	int *x=t,*y=t2;	memset(tong,0,sizeof(int)*range);	for(int i=0;i
         
          =0;--i) sa[--tong[x[i]]]=i;	for(int k=1;k<=n;k<<=1)	  {	  	int p=0;	  	for(int i=n-k;i
          
           =k) y[p++]=sa[i]-k; memset(tong,0,sizeof(int)*range); for(int i=0;i
           
            =0;--i) sa[--tong[x[y[i]]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; for(int i=1;i
            
             =n) break; range=p; }}void get_lcp(){ int k=0; for(int i=0;i
             
              =K) return 1; cnt=1; } else if(lcp[i]>=x) ++cnt; } return 0;}int main(){ scanf("%d%d",&n,&K); for(int i=0;i
              
               l) { int mid=(l+r+1>>1); if(check(mid)) l=mid; else r=mid-1; } printf("%d\n",l); return 0;}