by—cxlove
题目：给出一个串，求重复次数最多的连续重复子串
?id=3693
在后缀数组神文中也这题的题解。
比较容易理解的部分就是枚举长度为L，然后看长度为L的字符串最多连续出现几次。
既然长度为L的串重复出现，那么str[0],str[l],str[2*l]……中肯定有两个连续的出现在字符串中。
那么就枚举连续的两个，然后从这两个字符前后匹配，看最多能匹配多远。
即以str[i*l],str[i*l+l]前后匹配，这里是通过查询suffix(i*l),suffix(i*l+l)的最长公共前缀
通过rank值能找到i*l,与i*l+l的排名，我们要查询的是这段区间的height的最小值，通过RMQ预处理
达到查询为0(1)的复杂度，
设LCP长度为M, 则答案显然为M / L + 1, 但这不一定是最好的, 因为答案的首尾不一定再我们枚举的位置上. 我的解决方法是, 我们考虑M % L的值的意义, 我们可以认为是后面多了M % L个字符, 但是我们更可以想成前面少了(L – M % L)个字符! 所以我们求后缀j * L – (L – M % L)与后缀(j + 1) * L – (L – M % L)的最长公共前缀。
即把之前的区间前缀L-M%L即可。
然后把可能取到最大值的长度L保存，由于 题目要求字典序最小，通过sa数组进行枚举，取到的第一组，肯定是字典序最小的。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 100005#define maxn 100005using namespace std;//以下为倍增算法求后缀数组 int wa[maxn],wb[maxn],wv[maxn],Ws[maxn]; int cmp(int *r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];} void da(const char *r,int *sa,int n,int m){ int i,j,p,*x=wa,*y=wb,*t;for(i=0;i<m;i++) Ws[i]=0;for(i=0;i<n;i++) Ws[x[i]=r[i]]++;for(i=1;i<m;i++) Ws[i]+=Ws[i-1];for(i=n-1;i>=0;i–) sa[–Ws[x[i]]]=i;for(j=1,p=1;p<n;j*=2,m=p){for(p=0,i=n-j;i<n;i++) y[p++]=i;for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;for(i=0;i<n;i++) wv[i]=x[y[i]];for(i=0;i<m;i++) Ws[i]=0;for(i=0;i<n;i++) Ws[wv[i]]++;for(i=1;i<m;i++) Ws[i]+=Ws[i-1];for(i=n-1;i>=0;i–) sa[–Ws[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}return; } int sa[maxn],Rank[maxn],height[maxn]; //求height数组 void calheight(const char *r,int *sa,int n){ int i,j,k=0; for(i=1;i<=n;i++) Rank[sa[i]]=i; for(i=0;i<n;height[Rank[i++]]=k)for(k?k–:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++); return; }int dp[maxn][20];void Rmq_Init(int n){int m=floor(log(n+0.0)/log(2.0));for(int i=1;i<=n;i++) dp[i][0]=height[i];for(int i=1;i<=m;i++){for(int j=n;j;j–){dp[j][i]=dp[j][i-1];if(j+(1<<(i-1))<=n)dp[j][i]=min(dp[j][i],dp[j+(1<<(i-1))][i-1]);}}}int Rmq_Query(int l,int r){int a=Rank[l],b=Rank[r];if(a>b) swap(a,b);a++;int m=floor(log(b-a+1.0)/log(2.0));return min(dp[a][m],dp[b-(1<<m)+1][m]);}char str[maxn];int main(){int cas=0;while(scanf("%s",str)!=EOF&&str[0]!=’#’){int n=strlen(str);da(str,sa,n+1,130);calheight(str,sa,n);Rmq_Init(n);int cnt=0,mmax=0,a[maxn];for(int l=1;l<n;l++){for(int i=0;i+l<n;i+=l){int r=Rmq_Query(i,i+l);int step=r/l+1;int k=i-(l-r%l);if(k>=0&&r%l)if(Rmq_Query(k,k+l)>=r)step++;if(step>mmax){mmax=step;cnt=0;a[cnt++]=l;}else if(step==mmax)a[cnt++]=l;}}int len=-1,st;for(int i=1;i<=n&&len==-1;i++){for(int j=0;j<cnt;j++){int l=a[j];if(Rmq_Query(sa[i],sa[i]+l)>=(mmax-1)*l){len=l;st=sa[i];break;}}}printf("Case %d: ",++cas);for(int i=st,j=0;j<len*mmax;j++,i++) printf("%c",str[i]);printf("\n");}return 0;}
，收敛自己的脾气，偶尔要刻意沉默，
