#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 500050
using namespace std;
int n, s[MAXN], t1[MAXN], t2[MAXN], c[1000], sa[MAXN], height[MAXN], rank[MAXN];
void buildsa(){
	n++;
	int m = 600;
	int *x = t1, *y = t2;
	memset(c, 0, sizeof(c));
	for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
	for (int i = 1; i < m; i++) c[i] += c[i - 1];
	for (int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
	for (int k = 1; k <= n; k <<= 1){
		int p = 0;
		for (int i = n - k; i < n; i++) y[p++] = i;
		for (int i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;
		memset(c, 0, sizeof(c));
		for (int i = 0; i < n; i++) c[x[y[i]]]++;
		for (int i = 1; i < m; i++) c[i] += c[i - 1];
		for (int i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
		swap(x, y);
		p = 1;
		x[sa[0]] = 0;
		for (int i = 1; i < n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p - 1: p++;
//		for (int i = 0; i < n; i++) cout << y << ' ';
//		memcpy(rank, y, sizeof(y));
		if (p >= n) break;
		m = p;
	}
}

void getheight(){
//	cout << n << endl;
	for (int i = 0; i < n; i++) rank[sa[i]] = i;
	int h = 0;
//	height[0] = 0;
	for (int i = 0; i < n; i++){
		int j = sa[rank[i] - 1];
		if (h) h--;
		while(s[i + h] == s[j + h]) h++;
		height[rank[i]] = h;
	}
}

bool findx(int k){
	int minn, maxn;
	minn = maxn = sa[0];
	for (int i = 0; i < n; i++){
		if (height[i] < k){
			minn = maxn = sa[i];
			continue;
		}
		maxn = max(maxn, sa[i]);
		minn = min(minn, sa[i]);
		if (maxn - minn > k) return 1;
	}
	return 0;
}

int main(){
//	freopen("c.in", "r", stdin);
//	freopen("c.out", "w", stdout);
	while(~scanf("%d", &n)){
		if (n == 0) break;
		for (int i = 0; i < n; i++) scanf("%d", &s[i]);
		if (n < 10){
			printf("0\n");
			continue;
		}
		n--;
		for (int i = 0; i < n; i++) s[i] = s[i + 1] - s[i] + 300;
		s[n] = 0;
//		cout << n << endl;
		buildsa();
		getheight();
//		for (int i = 0; i < n; i++) cout << sa[i] << ' ';
		int l = 0, r = n;
		while(l < r){
			int mid = (l + r + 1) >> 1;
			if (findx(mid)) l = mid;
			else r = mid - 1;
//			cout << "(" << l << ", " << r << ")";
		}
		printf("%d\n", l < 4? 0: l + 1);
	}
}

RT 随机生成了100+M超范围的数据 就是没一个RE。。 一上POJ就RE了 求解Orz

• Re:无限RE！！求dalao来看看小弟的代码Orz (9) aclolicon 2016-08-08 11:18:14