题目大意：给定一个字符串，求它的最长可重叠的重复子串的长度
思路：求出height数组之后，输出最大值即可。因为最长可重叠的重复子串一定是在相邻两个后缀的最长公共前缀，即height，而要求最大值，输出height最大值即可
#include#include #define max(a,b) a>b?a:busing namespace std;const int maxl=400000;int sa[maxl+10],tsa[maxl+10],rank[maxl+10],trank[maxl+10],sum[maxl+10],n,h[maxl+10];char s[maxl+10];void sorts(int j){ memset(sum,0,sizeof(sum)); for (int i=1;i<=n;i++) sum[rank[i+j]]++; for (int i=1;i<=n;i++) sum[i]+=sum[i-1]; for (int i=n;i>0;i--) tsa[sum[rank[i+j]]--]=i; memset(sum,0,sizeof(sum)); for (int i=1;i<=n;i++) sum[rank[tsa[i]]]++; for (int i=1;i<=n;i++) sum[i]+=sum[i-1]; for (int i=n;i>0;i--) sa[sum[rank[tsa[i]]]--]=tsa[i];}void getsa(){ for (int i=1;i<=n;i++) trank[i]=s[i]; for (int i=1;i<=n;i++) sum[trank[i]]++; for (int i=1;i<=255;i++) sum[i]+=sum[i-1]; for (int i=n;i>0;i--) sa[sum[trank[i]]--]=i; rank[sa[1]]=1; for (int i=2,p=1;i<=n;i++){ if (trank[sa[i]]!=trank[sa[i-1]]) p++; rank[sa[i]]=p; } for (int j=1;j<=n;j*=2){ sorts(j); trank[sa[1]]=1; for (int i=2,p=1;i<=n;i++){ if (rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+j]!=rank[sa[i-1]+j]) p++; trank[sa[i]]=p; } memcpy(rank,trank,sizeof(rank)); }}void geth(){ for (int i=1,j=0;i<=n;i++){ if (rank[i]==1) continue; while (s[i+j]==s[sa[rank[i]-1]+j]) j++; h[rank[i]]=j; if (j>0) j--; }}int main(){ scanf("%d",&n); scanf("%s",s+1); getsa(); geth(); int maxs=0; for (int i=1;i<=n;i++) maxs=max(maxs,h[i]); printf("%d\n",maxs); //for (;;); return 0;}