后缀数组第一题。 这道题要的是 重复至少K次的 最长子串。 先把后缀数组中的height数组处理出来，这个套模板就可以了。
然后接下来二分答案ans，然后扫描height数组，看看有没有是否有k-1个height[i]>=ans 有的话就是可以，否则继续做。
关于模板有个要注意的地方： （至少我手上的是这样），需要在待处理数组后面加一个比所有字符都小的数字/字符，这样是为了防止无法比较。例如 222和222222这种情况，加了之后不会RE。如果是2220和222220，那这样的话一定可以比较出来的。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int nMax = 1200001; int num[nMax]; int arr[nMax+1]; int sa[nMax], rank[nMax], height[nMax]; int wa[nMax], wb[nMax], wv[nMax], wd[nMax]; int n,k; int cmp(int *r, int a, int b, int l){ return r[a] == r[b] && r[a+l] == r[b+l]; } void da(int *r, int n, int m){ // 倍增算法 r为待匹配数组 n为总长度 m为字符范围 int i, j, p, *x = wa, *y = wb, *t; for(i = 0; i < m; i ++) wd[i] = 0; for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++; for(i = 1; i < m; i ++) wd[i] += wd[i-1]; for(i = n-1; i >= 0; i --) sa[-- wd[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 ++) wd[i] = 0; for(i = 0; i < n; i ++) wd[wv[i]] ++; for(i = 1; i < m; i ++) wd[i] += wd[i-1]; for(i = n-1; i >= 0; i --) sa[-- wd[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 ++; } } } void calHeight(int *r, int n){ // 求height数组。 int i, j, k = 0; for(i = 1; i <= n; i ++) { rank[sa[i]] = i; //cout<<sa[i]<<endl; } 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 ++); } } bool test(int len,int n) { for(int i=n;;) { int tt=0; int j=i; if(i<=0) break; while(j>=1) { if(height[j]>=len) { if(tt==0) tt+=2; else tt++; if(tt>=k) return true; j--; } else { i=j-1; break; } } } return false; } int main() { while(cin>>n>>k) { for(int i=0;i<n;i++) scanf("%d",&num[i]); for(int i=0;i<n;i++) num[i]++; num[n]=0; da(num,n+1,1000002); calHeight(num,n); if(k>n) { cout<<0<<endl; continue; } int l=0; int r=n; int ans=0; while(l<=r) { int mid=(l+r)/2; if(test(mid,n)==true) { ans=max(ans,mid); l=mid+1; } else r=mid-1; } cout<<ans<<endl; } return 0; }