Milk Patterns 产奶的模式 bzoj-1717 Usaco-2006 Dec

题目大意：给定一个字符串，求最长的至少出现了$k$次的子串长度。

注释：$1\le n\le 2\cdot 10^4$，$2\le k\le n$。

想法：不难想到二分答案，现在我们考虑如何验证。

这里就是后缀数组的一个妙用了。

我们对原串建立后缀数组，观察$ht$数组。

考虑当前二分出来的$mid$。如果有至少连续$k$的$ht$值都不小于$mid$，那么$k$就是合法的。

故此我们直接扫$ht$数组看看最长的连续比$mid$大的$ht$有多少个即可。

Code：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 1000010 using namespace std;int wv[N],wa[N],sa[N],Ws[N],wb[N],t[N],rk[N],ht[N],r[N];int n,m=1000009;inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}void build_sa(){	int i,j,p,*x=wa,*y=wb,*t;	for(i=0;i
         
          =0) y[p++]=sa[i]-j;		for(i=0;i
          
           
             void Max(T &x,T y) {x=max(x,y);}// inline void Max(int &x,int y) {x=max(x,y);}int check(int x){ int re=-1,now=0; for(int i=0;i
            
             =x) now++; else Max(re,now),now=1; } Max(re,now); return re;}int main(){ n=rd();int k=rd(); for(int i=0;i
             
              >1; if(check(mid)>=k) l=mid+1; else r=mid; } l--; cout << l << endl ; return 0;}