D – Milk Patterns （出现k次可重复的最长子串的长度）

题目链接：https://cn.vjudge.net/contest/283743#problem/D

题目大意：给你n个数，然后问你出现m次的最长子串的长度。

具体思路：和上一篇博客的内容差不多，这个是可重复的，就不需要考虑sa的问题了，每一次还是二分答案，判断出现的最长前缀就可以了。注意二分的时候，每一次的寻找，初始值为1，因为这个字符串就已经出现过一次了。

AC代码：

 #include<iostream>
 #include<stack>
 #include<cstring>
 #include<iomanip>
 #include<stdio.h>
 #include<algorithm>
 #include<cmath>
 using namespace std;
 # define ll long long
 # define inf 0x3f3f3f3f
 const int maxn = 5e6+;
 int cntA[maxn], cntB[maxn], sa[maxn], tsa[maxn], A[maxn], B[maxn], height[maxn];
 int Rank[maxn];
 int ch[maxn];
 int sto[maxn];
 ll n,m;
 //sa[i]代表第i小的后缀位置，Rank[i]代表第i位置的后缀，排名第几小
 // height[i]代表排名第i个字符串和第i-1个字符串的相同前缀有多少个
 void cal(int maxx)
 {
     for(int i = ; i <=maxx; i++)
         cntA[i] = ;
     //   cout<<1<<endl;
     //  cout<<n<<endl;
     for(int i = ; i <= n; i++)
     {
         //cout<<ch[i-1]<<endl;
         cntA[ch[i-]]++;
     }
     //  cout<<1<<endl;
     for(int i = ; i <= maxx; i++)
         cntA[i] += cntA[i-];
     for(int i = n; i; i--)
         sa[cntA[ch[i-]]--] = i;
     Rank[sa[]] = ;
     for(int i = ; i <= n; i++)
     {
         Rank[sa[i]] = Rank[sa[i-]];
         if(ch[sa[i]-] != ch[sa[i-]-])
             Rank[sa[i]]++;
     }
     for(int l = ; Rank[sa[n]] < n; l <<= )
     {
         memset(cntA, , sizeof(cntA));
         memset(cntB, , sizeof(cntB));
         for(int i = ; i <= n; i++)
         {
             cntA[A[i] = Rank[i]]++;
             cntB[B[i] = (i+l <= n)?Rank[i+l]:]++;
         }
         for(int i = ; i <= n; i++)
             cntB[i] += cntB[i-];
         for(int i = n; i; i--)
             tsa[cntB[B[i]]--] = i;
         for(int i = ; i <= n; i++)
             cntA[i] += cntA[i-];
         for(int i = n; i; i--)
             sa[cntA[A[tsa[i]]]--] = tsa[i];
         Rank[sa[]]=;
         for(int i = ; i <= n; i++)
         {
             Rank[sa[i]] = Rank[sa[i-]];
             if(A[sa[i]] != A[sa[i-]] || B[sa[i]] != B[sa[i-]])
                 Rank[sa[i]]++;
         }
     }
     for(int i = , j = ; i <= n; i++)
     {
         if(j)
             j--;
         while(ch[i+j-] == ch[sa[Rank[i]-] + j - ])
             j++;
         height[Rank[i]] = j;
     }
 }
 bool judge(int t)
 {
     int ans=;
     for(int i=; i<=n; i++)
     {
         if(height[i]>=t)
         {
             ans++;
         }
         else
         {
             ans=;
         }
         if(ans>=m)
             return true;
     }
     return false;
 }
 int main()
 {
     int maxx=;
     scanf("%lld %lld",&n,&m);
     for(int i=; i<=n; i++)
     {
         scanf("%d",&ch[i]);
         maxx=max(maxx,ch[i]);
     }
     cal(maxx);
     int l=,r=1e8,ans=;
     while(l<=r)
     {
         int mid=(l+r)>>;
         if(judge(mid))
         {
             ans=mid;
             l=mid+;
         }
         else
         {
             r=mid-;
         }
     }
     printf("%d\n",ans);
     return ;
 }