重复次数最多的连续重复子串

题目链接：https://cn.vjudge.net/contest/318888#problem/G

 

题意：

给定一个字符串，求重复次数最多的连续重复子串

 

思路：

我们先看下罗老师的论文中给出的思路

 

虽然话很短，但是很难理解。我就讲一下我刚开始无法理解的一些地方吧，既方便我巩固也方便我今后复习。

 

1、为什么连续出现了K/L+1次？

我们先看这个图片上的例子

r[6] :  a a b a a b a a b a b

r[9] :  a a b a a b a b

先考虑往后匹配可以知道K=9，K/L只是在 r[9]之后重复出现的次数 再加上 r[6]->r[9]之间重复出现的一次

所以是 K/L+1

 

2、为什么S肯定包括了字符r[0],r[L],r[2*L] 中某相邻两个

由于当前S是有两个长度为L的连续重复子串拼接而成的，那意味着S[i]和S[i+L](0≤i<L)必定是一样的字符

而这两个字符位置相差L

而字符r[0],r[L],r[L*2],r[L*3],......中相邻两个的位置差均为L

 

3、为什么只须看字符r[L*i]和r[L*(i+1)]往前和往后各能匹配到多远

其实，当枚举的重复子串长度为i时，我们在枚举r[i*j]和r[i*(j+1)]的过程中，必然可以出现r[i*j]在第一个重复子串里，而r[i*(j+1)]在第二个重复子串里的这种情况，如果此时r[i*j]是第一个重复子串的首字符，这样直接用公共前缀k除以i并向下取整就可以得到最后结果。但如果r[i*j]如果不是首字符，这样算完之后结果就有可能偏小，因为r[i*j]前面可能还有少许字符也能看作是第一个重复子串里的。

于是，我们不妨先算一下，从r[i*j]开始，除匹配了k/i个重复子串，还剩余了几个字符，剩余的自然是k%i个字符。如果说r[i*j]的前面还有i-k%i个字符完成匹配的话，这样就相当于利用多余的字符还可以再匹配出一个重复子串，于是我们只要检查一下从r[i*j-(i-k%i)]和r[i*(j+1)-(i-k%i)]开始是否有i-k%i个字符能够完成匹配即可，也就是说去检查这两个后缀的最长公共前缀是否比i-k%i大即可。
当然如果公共前缀不比i-k%i小，自然就不比i小，因为后面的字符都是已经匹配上的，所以为了方便编写，程序里面就直接去看是否会比i小就可以了。

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <string.h>
  5 #include <stdlib.h>
  6 #include <math.h>
  7 #include <queue>
  8 #include <set>
  9 
 10 #define INF 0x3f3f3f3f
 11 #define pii pair<int,int>
 12 #define LL long long
 13 using namespace std;
 14 typedef unsigned long long ull;
 15 const int maxn = 5e4 + 10;
 16 
 17 char s[maxn];
 18 int sa[maxn],t[maxn],t2[maxn],c[maxn];
 19 int Rank[maxn],height[maxn];
 20 int dp[maxn][maxn];
 21 
 22 void build_sa(int n,int m)
 23 {
 24     int i,j,*x=t,*y=t2;
 25     for (i=0;i<m;i++)
 26         c[i] = 0;
 27     for (i=0;i<n;i++)
 28         c[x[i] = s[i]]++;
 29     for (i=1;i<m;i++)
 30         c[i] += c[i-1];
 31     for (i=n-1;i>=0;i--)
 32         sa[--c[x[i]]] = i;
 33     for (int k=1;k<=n;k<<=1)
 34     {
 35         int p = 0;
 36         for (i=n-k;i<n;i++)
 37             y[p++] = i;
 38         for (i=0;i<n;i++)
 39         {
 40             if (sa[i]>=k)
 41                 y[p++] = sa[i]-k;
 42         }
 43         for (i=0;i<m;i++)
 44             c[i] = 0;
 45         for (i=0;i<n;i++)
 46             c[x[y[i]]]++;
 47         for (i=1;i<m;i++)
 48             c[i] += c[i-1];
 49         for (i=n-1;i>=0;i--)
 50             sa[--c[x[y[i]]]] = y[i];
 51         swap(x,y);
 52         p = 1;
 53         x[sa[0]] = 0;
 54         for (i=1;i<n;i++)
 55             x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
 56         if (p>=n)
 57             break;
 58         m = p;
 59     }
 60 }
 61 
 62 void getHeight(int n){
 63     int i,j,k=0;
 64     for (i=1;i<=n;i++){
 65         Rank[sa[i]] = i;
 66     }
 67     for (i=0;i<n;i++){
 68         if (k)
 69             k--;
 70         j = sa[Rank[i]-1];
 71         while (s[i+k] == s[j+k])
 72             k++;
 73         height[Rank[i]] = k;
 74     }
 75 }
 76 
 77 void ST_build(int n){
 78     for (int i=0;i<n;i++){
 79         dp[i][0] = height[i];
 80     }
 81     for (int j=1;(1<<j)<=n;j++){
 82         for (int i=0;(i+(1<<j)-1)<=n;i++){
 83             dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
 84         }
 85     }
 86 }
 87 
 88 int querry(int i,int j){
 89     int l = min(Rank[i],Rank[j]);
 90     int r = max(Rank[i],Rank[j]);
 91     l++;
 92     int cnt = log2(r-l+1),len = 1<<cnt;
 93     return min(dp[l][cnt],dp[r-len+1][cnt]);
 94 }
 95 
 96 
 97 int main(){
 98     int T;
 99     scanf("%d",&T);
100     while (T--){
101         int maxx = 1;
102         int n;
103         scanf("%d",&n);
104         getchar();
105         for (int i=0;i<n;i++){
106             scanf("%c",&s[i]);
107             getchar();
108         }
109         s[n] = 0;
110         build_sa(n+1,100);
111         getHeight(n);
112         ST_build(n+1);
113         for (int i=1;i<=n;i++){
114             for (int j=0;j+i<n;j+=i){
115                 int ans = querry(j,j+i);
116                 int k = j-(i-ans%i);
117                 ans = ans/i+1;
118                 if (k>=0 && querry(k,k+i)>=i)
119                     ans++;
120                 maxx = max(maxx,ans);
121             }
122         }
123         printf("%d\n",maxx);
124     }
125     return 0;
126 }