【题目分析】
其实找最长的不重叠字串是很容易的，后缀数组+二分可以在nlogn的时间内解决。
但是转调是个棘手的事情。
其实只需要o(*￣▽￣*)ブ差分就可以了。
背板题。
【代码】
#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <map>#include <set>#include <queue>#include <string>#include <iostream>#include <algorithm>using namespace std;#define maxn 50005#define inf 0x3f3f3f3f#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)void Finout(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); #endif}int Getint(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}struct SuffixArray{int s[maxn];int tmp[maxn],cnt[maxn],sa[maxn],rk[maxn],h[maxn];void build(int n,int m){int i,j,k;n++;F(i,0,2*n+5) tmp[i]=sa[i]=rk[i]=h[i]=0;F(i,0,m-1) cnt[i]=0;F(i,0,n-1) cnt[rk[i]=s[i]]++;F(i,1,m-1) cnt[i]+=cnt[i-1];F(i,0,n-1) sa[--cnt[rk[i]]]=i;for (k=1;k<=n;k<<=1){F(i,0,n-1){j=sa[i]-k;if (j<0) j+=n;tmp[cnt[rk[j]]++]=j;}sa[tmp[cnt[0]=0]]=j=0;F(i,1,n-1){if (rk[tmp[i]]!=rk[tmp[i-1]]||rk[tmp[i]+k]!=rk[tmp[i-1]+k]) cnt[++j]=i;sa[tmp[i]]=j;}memcpy(rk,sa,n*sizeof(int));memcpy(sa,tmp,n*sizeof(int));if (j>=n-1) break;}for (j=rk[h[i=k=0]=0];i<n-1;++i,++k)while (~k&&s[i]!=s[sa[j-1]+k]) h[j]=k--,j=rk[sa[j]+1];}}arr;int N,a[maxn];bool test(int k,int n){int minn=arr.sa[1],maxx=arr.sa[1];F(i,2,n){if (arr.h[i]>=k&&i<n){minn=min(arr.sa[i],minn);maxx=max(arr.sa[i],maxx);continue;}if (maxx-minn>=k) return true;minn=arr.sa[i];maxx=arr.sa[i];}return false;}int main(){ Finout(); while (scanf("%d",&N)!=EOF&&N) { F(i,0,N-1) scanf("%d",&a[i]); F(i,0,N-2) arr.s[i]=a[i]-a[i+1]+89; arr.s[N-1]=0; arr.build(N-1,200); int l=3,r=(N-2)/2; while (l<r) { int mid=(l+r)/2+1; if (test(mid,N-1)) l=mid; else r=mid-1;}printf("%d\n",l<4?0:l+1);}}
