求一个字符串中一个连续重复子串的最大重复次数。
首先枚举这个子串的长度l。 那么显然，它们一定要经过0,l,2l,3l,……之中至少一个点。 枚举这个观察点il，让后缀il与后缀(i+1)l求LCP，可以用SA完成，接着假设LCP为k，那么k/l+1这个答案是合法的（可以自己动手画一画，就很容易知道），不过，有可能两个字符串不从观察点开始匹配，也就是再左移l-k%l还能再匹配一段（即答案是k/l+2），左移再求LCP检验答案是否能加一即可。
#include<cstdio> #include<algorithm> #include<cmath> #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; const int maxn=50000+10; typedef long long ll; int a[maxn]; int sa[maxn],rank[maxn*2],height[maxn],b[maxn],c[maxn],d[maxn]; int rmq[maxn][20]; int i,j,k,l,r,t,n,m,ca,ans; char get(){ char ch=getchar(); while (ch<'a'||ch>'b') ch=getchar(); return ch; } void getsa(){ fo(i,1,n) rank[i]=a[i]; j=1; while (j<=n){ fo(i,0,n) b[i]=0; fo(i,1,n) b[rank[i+j]]++; fo(i,1,n) b[i]+=b[i-1]; fd(i,n,1) c[b[rank[i+j]]--]=i; fo(i,0,n) b[i]=0; fo(i,1,n) b[rank[c[i]]]++; fo(i,1,n) b[i]+=b[i-1]; fd(i,n,1) d[b[rank[c[i]]]--]=c[i]; t=0; fo(i,1,n){ if (rank[d[i]]!=rank[d[i-1]]||rank[d[i]+j]!=rank[d[i-1]+j]) t++; c[d[i]]=t; } fo(i,1,n) rank[i]=c[i]; if (t==n) break; j*=2; } fo(i,1,n) sa[rank[i]]=i; } void getheight(){ k=0; fo(i,1,n){ if (k) k--; j=sa[rank[i]-1]; while (i+k<=n&&j+k<=n&&a[i+k]==a[j+k]) k++; height[rank[i]]=k; } } int lcp(int i,int j){ if (i<=0||j<=0) return 0; if (rank[i]>rank[j]) swap(i,j); int k=floor(log(rank[j]-rank[i])/log(2)); return min(rmq[rank[i]+1][k],rmq[rank[j]-(1<<k)+1][k]); } int main(){ scanf("%d",&ca); while (ca--){ scanf("%d",&n); fo(i,1,n*2) rank[i]=0; fo(i,1,n) a[i]=get()-'a'+1; getsa(); getheight(); fo(i,1,n) rmq[i][0]=height[i]; fo(j,1,floor(log(n)/log(2))) fo(i,1,n-(1<<j)+1) rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]); ans=1; fo(j,1,n/2){ if (n/j+2<=ans) break; fo(i,1,n/j-1){ k=lcp((i-1)*j+1,i*j+1); if (k/j+2<=ans) continue; ans=max(ans,k/j+1); r=j-k%j; if (r&&lcp((i-1)*j+1-r,i*j+1-r)>=j) ans=max(ans,k/j+2); } } printf("%d\n",ans); } }