题意：
楼教主男人8题里的一题。
给出一串数，让你找出最长的两段不重合的连续差值相等的子串。
分析：
先令S[I]=A[I]-A[I-1]，然后问题转化为求S[I]的最长不重合重复子串。
先用后缀数组处理好S[I]，然后二分答案分组，如果某一组里的MAX(SA[I])-MIN(SA[J])>LIMIT，表示这组可以找到不重合的答案。
然后输出即可。
插曲：
有一个地方Gn打成n了。WA了N久。
code：
#include
#define min(x,y) (x)<(y)?(x):(y)
const int N=22222;
struct gtp{int x,data[3],next;}g[N];
int n,s[N],sa[N],rank[N],height[N],a[N][3],ls[N],e;
int G[N],pu[20][N],pd[20][N],tmp[N],lg[N];
void init(){
for (int i=0;i
int t=0; lg[1]=0;
for (int i=1;i<=n;i++)
if (1<
}
inline void add(int x,int data[]){
e++;
g[e].x=x; g[e].next=ls[x]; ls[x]=e;
memcpy(g[e].data,data,sizeof(a[0]));
}
void Jsort(){
for (int k=1;k>=0;k–){
e=0;
for (int i=0;i<=n;i++) ls[i]=0;
for (int i=n;i>=1;i–) add(a[i][k],a[i]);
int tail=0;
for (int i=0;i<=n;i++)
for (int t=ls[i];t!=0;t=g[t].next)
memcpy(a[++tail],g[t].data,sizeof(a[0]));
}
}
void Sort(int l,int r){
if (l>=r) return;
int i=l,j=r,mid=s[sa[l+r>>1]],temp;
while (i
if (i<=j){
temp=sa[i]; sa[i]=sa[j]; sa[j]=temp;
i++; j–;
}
}
Sort(l,j);
Sort(i,r);
}
void build(){
for (int i=1;i<=n;i++) sa[i]=i;
Sort(1,n);
int tail=0;
for (int i=1;i<=n;i++){
if (i==1 || s[sa[i]]!=s[sa[i-1]]) tail++;
rank[sa[i]]=tail;
}
for (int k=1;1<
a[i][0]=rank[i];
if (i+(1<
a[i][2]=i;
}
Jsort();
tail=0;
for (int i=1;i<=n;i++){
if (i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) tail++;
rank[a[i][2]]=tail;
}
}
for (int i=1;i<=n;i++) sa[rank[i]]=i;
}
void Sparse_Table(){
for (int i=1;i<=n;i++) pu[0][i]=sa[i];
for (int i=1;i<=n;i++) pd[0][i]=sa[i];
for (int k=1;1<
}
inline int Maxsa(int l,int r){
int t=lg[r-l+1];
return max(pu[t][l],pu[t][r-(1<
inline int Minsa(int l,int r){
int t=lg[r-l+1];
return min(pd[t][l],pd[t][r-(1<
void MakeHeight(){
for (int i=0;i<=n;i++) height[i]=0;
for (int i=1;i<=n;i++){
if (rank[i]==1) continue;
int st=max(height[rank[i-1]]-1,0),j=i+st,k=sa[rank[i]-1]+st;
while (j<=n && k<=n && s[j]==s[k]){st++;j++;k++;}
height[rank[i]]=st;
}
}
bool flag(int limit){
int Gn=1; G[1]=1;
for (int i=2;i<=n;i++)
if (height[i]>=limit) G[i]=Gn;
else G[i]=++Gn;
int j=1;
for (int i=1;i<=Gn;i++){
int st=j;
while (j<=n && G[j]==i) j++;
int ed=j-1;
if (Maxsa(st,ed)-Minsa(st,ed)>limit) return true;
}
return false;
}
int binary(){
int l=0,r=n,mid;
while (l+1
if (flag(mid)) l=mid;
else r=mid-1;
}
if (flag(r)) return r;
return l;
}
int main(){
while (scanf("%d",&n) && n!=0){
init();
build();
Sparse_Table();
MakeHeight();
int ans=binary();
if (ans<4) printf("0n");
else printf("%dn",ans+1);
}
}
