这题是罗大神的论文题= =求重复k次的最长子串。 求出height以后二分判断或者单调队列都是可以的，我选择二分w。 实力诠释一波眼瞎，判断一个n打成n-1调了半天。。
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e6+5; int sa[N],rank[N],height[N],nsa[N],nrank[N],sum[N]; int s[N]; int n,k; inline void sort(int j) { memset(sum,0,sizeof(sum)); fo(i,1,n)sum[rank[i+j]]++; fo(i,1,n)sum[i]+=sum[i-1]; fd(i,n,1)nsa[sum[rank[i+j]]--]=i; memset(sum,0,sizeof(sum)); fo(i,1,n)sum[rank[i]]++; fo(i,1,n)sum[i]+=sum[i-1]; fd(i,n,1)sa[sum[rank[nsa[i]]]--]=nsa[i]; } inline void gsa() { memset(sum,0,sizeof(sum)); fo(i,1,n)rank[i]=s[i]; fo(i,1,n)sum[rank[i]]++; fo(i,1,N)sum[i]+=sum[i-1]; fd(i,n,1) sa[sum[rank[i]]--]=i; int p=1; fo(i,2,n) nrank[sa[i]]=rank[sa[i]]==rank[sa[i-1]]?p:++p; for(int j=1;j<=n;j*=2) { sort(j); p=1; fo(i,2,n) { if (rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+j]!=rank[sa[i-1]+j])p++; nrank[sa[i]]=p; } fo(i,1,n)rank[i]=nrank[i]; } } inline void getheight() { int k=0; fo(i,1,n) { if (k)k--; int j=sa[rank[i]-1]; while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++; height[rank[i]]=k; } } inline bool pd(int x) { int sum=0; fo(i,1,n-1) { if (height[i]>=x) { sum++; if (sum==k-1)return 1; } else sum=0; } return 0; } int num[N],hash[N],tot; inline int find(int x) { int l=1,r=tot,ans=0; while (l<=r) { int mid=(l+r)>>1; if (hash[mid]<=x)ans=mid,l=mid+1; else r=mid-1; } return ans; } int main() { scanf("%d%d",&n,&k); fo(i,1,n)scanf("%d",&s[i]),num[i]=s[i]; sort(num+1,num+n+1); hash[++tot]=num[1]; fo(i,2,n)if (num[i]!=num[i-1])hash[++tot]=num[i]; fo(i,1,n)s[i]=find(s[i]); gsa(); getheight(); int l=1,r=n,ans=0; while (l<=r) { int mid=(l+r)>>1; if (pd(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans); }