Chrysanthemum's Blog

题意：给你一个数字串，找到最长长度且不重叠的两个子串，使得这两个子串变化相同。

什么叫变化相同呢，就是比如{1,3,4,6,9}与{5,7,8,10,13}就是变化相同的。

首先我们可以把数字串的相邻两个相减，得到的新序列。我们只要在这个新序列中找到最长的相等的且不重叠的两个子串。我们可以先二分答案，然后由于lcp的性质，height可以分为若干组，每组中的height都是大于等于mid的，只要同一组存在两个数使得它们在原串的的位置差大于mid，就可行。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,x,y;
int wa[20010],wb[20010],ws[20010],wv[20010],r[20010],sa[20010],rank[20010],height[20010];
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 *sa,int n,int m)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for (i=0;i<m;i++) ws[i]=0;
	for (i=0;i<n;i++) ws[x[i]=r[i]]++;
	for (i=1;i<m;i++) ws[i]+=ws[i-1];
	for (i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
	for (j=1,p=1;p<n;j*=2,m=p)
	{
		p=0;
		for (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++) ws[i]=0;
		for (i=0;i<n;i++) ws[wv[i]]++;
		for (i=1;i<m;i++) ws[i]+=ws[i-1];
		for (i=n-1;i>=0;i--) sa[--ws[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 *sa,int n)
{
	int i,j,k=0;
	for (i=1;i<=n;i++) rank[sa[i]]=i;
	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++);
}
int check(int *sa,int n,int mid)
{
	int Min=sa[1],Max=sa[1];
	for (int i=2;i<=n;i++)
	{
		if (height[i]<mid) Min=Max=sa[i];else
		{
			Max=max(Max,sa[i]);
			Min=min(Min,sa[i]);
			if (Max-Min>mid) return 1;
		}
	}
	return 0;
}
int main()
{
	while (1)
	{
		scanf("%d",&n);
		if (!n) break;
		scanf("%d",&y);
		n--;
		for (int i=0;i<n;i++)
		{
			scanf("%d",&x);
			r[i]=x-y+100;
			y=x;
		}
		r[n]=0;
		da(r,sa,n+1,200);
		calheight(r,sa,n);
		int l=1,r=n/2;
		while (l<r)
		{
			int mid=((l+r)>>1)+1;
			if (check(sa,n,mid)) l=mid;else r=mid-1;
		}
		if (r>=4) printf("%d\n",r+1);else printf("0\n");
	}
}