H - Repeats （重复最多子串的次数）

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

题目大意：T组数据，给你一个字符串，然后让你求这个字符串的重复最多子串的次数。

具体思路：论文题。

https://www.cnblogs.com/staginner/archive/2012/02/06/2340521.html。

rmq处理的是某区间内的最小的前缀长度，这样查询的时候直接找到这个区间内的最小值就可以了。

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 = 5e5+;

 int cntA[maxn], cntB[maxn], sa[maxn], tsa[maxn], A[maxn], B[maxn], height[maxn];

 int Rank[maxn],dp[][maxn];

 char ch[maxn];

 int sto[maxn];

 ll n;

 //sa[i]代表第i小的后缀位置，Rank[i]代表第i位置的后缀，排名第几小

 // height[i]代表排名第i个字符串和第i-1个字符串的相同前缀有多少个

 void cal()

 {

     for(int i = ; i < ; 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 < ; 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;

     }

 }

 void rmq()

 {

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

     {

         dp[][i]=height[i];

     }

     int tmp=log2(n);

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

     {

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

         {

             dp[i][j]=min(dp[i-][j],dp[i-][j+(<<(i-))]);

         }

     }

 }

 int query(int t1,int t2)

 {

     t1=Rank[t1];

     t2=Rank[t2];

     if(t1>t2)

         swap(t1,t2);

     t1++;

     int tmp=log2(t2-t1+);

     return min(dp[tmp][t1],dp[tmp][t2-(<<tmp)+]);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         char u;

         scanf("%d",&n);

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

         {

             getchar();

             scanf("%c",&u);

             ch[i]=u;

         }

 //cout<<ch<<endl;

         cal();

         rmq();

         int ans=,t1,t2,t;

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

         {

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

             {

                 int tmp=query(j,j+i);

                 t1=i-tmp%i;

                 t2=j-t1;

                 t=tmp/i+;

                 if(t2>&&query(t2,t2+i)>=t1)

                     t++;

                 ans=max(ans,t);

             }

         }

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

     }

     return ;

 }