poj_3261_Milk Patterns(后缀数组)

时间：2021-04-30 06:49:31

题目链接：poj_3261_Milk Patterns

题意：

给你一串数，让你找重复出现不少于k次的子串的最长长度，重复出现可重叠

题解：

老套路，还是二分答案，然后用height数组来check答案

 #include<cstdio>

 #include<algorithm>

 #define F(i,a,b) for(int i=a;i<=b;i++)

 using namespace std;

 namespace suffixarray{

     #define FN(n) for(int i=0;i<n;i++)

     const int N =2E5+;

     int rnk[N],sa[N],height[N],c[N],s[N];

     void getsa(int n,int m,int *x=rnk,int *y=height){

         FN(m)c[i]=;FN(n)c[x[i]=s[i]]++;FN(m)c[i+]+=c[i];

         for(int i=n-;i>=;i--)sa[--c[x[i]]]=i;

         for(int k=,p;p=,k<=n;k=p>=n?N:k<<,m=p){

             for(int i=n-k;i<n;i++)y[p++]=i;

             FN(n)if(sa[i]>=k)y[p++]=sa[i]-k;

             FN(m)c[i]=;FN(n)c[x[y[i]]]++;FN(m)c[i+]+=c[i];

             for(int i=n-;i>=;i--)sa[--c[x[y[i]]]]=y[i];

             swap(x,y),p=,x[sa[]]=;

             for(int i=;i<n;i++)

             x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;

         }

         FN(n)rnk[sa[i]]=i;

         for(int i=,j,k=;i<n-;height[rnk[i++]]=k)

         for(k=k?k-:k,j=sa[rnk[i]-];s[i+k]==s[j+k];k++);

     }

 }

 using namespace suffixarray;

 int n,k,a[N],ed;

 inline int getid(int x){return lower_bound(a+,a++ed,x)-a;}

 bool check(int x,int cnt=)

 {

     F(i,,n)if(height[i]>=x){if(++cnt>=k)return ;}else cnt=;

     return ;

 }

 int main()

 {

     while(~scanf("%d%d",&n,&k))

     {

         F(i,,n)scanf("%d",a+i),s[i-]=a[i];

         sort(a+,a++n),ed=;

         F(i,,n)if(a[i]!=a[ed])a[++ed]=a[i];

         F(i,,n-)s[i]=getid(s[i]);

         s[n]=,getsa(n+,ed+);

         int l=,r=n,mid,ans=;

         while(l<=r)mid=(l+r)>>,check(mid)?l=(ans=mid)+:r=mid-;

         printf("%d\n",ans);

     }

     return ;

 }

相关文章