不可重叠串

题目链接：ybt金牌导航2-2-2

题目大意

给你一个数组，要你找两个长度相等，互不相交的两个连续部分，使得一个部分可以通过所有数加或减一个数得到的第二个部分。

思路

首先我们看到是把所有数加或减一个值得到另外一个，那我们其实就是那两个部分的波动是一样的。

那你可以求出这个数比前面那个数大或小了多少。然后如果一直都是对上的，那这两个部分就可以选，如果对上的数的长度是 $n$，那这两个部分的长度就是 $n+1$。（因为每两个数之间才会产生相差的数一个）

那你把每个数组看成一种字符，它就相当于在一堆字符串里面找两个最长的不相交的一样的串。
那你其实可以这样做，求 SA 后缀数组，然后把关键的 height 数组求出。

那你其实就相当于找两个地方作为起点，然后用 height 求出这两个为起点的最长公共前缀，然后判断相交，在不相交的之间取长度最大值。
但是很明显它超时了。

那你看到求的是最长公共前缀，那我们在想到求最长公共前缀就是枚举排名然后取 $\min$，我们可以考虑二分能的长度。
那我们就枚举排名，会把它分成一些区间，每个区间里面取 $\min$ 值一定会大于等于你二分的值。（而且再往外扩张就不满足）

那也就是说，对于某个区间的里面的每个位置，从它们之间选任意两个位置作为开始，最长公共前缀一定是大于等于你二分要判断的值，那你就只要看是否有不会相交的就可以。
至于如何判断相交，你就找这个区间里面位置最前和最后的（因为这两个最不容易相交），至于怎么判断相交，最前面的是 $minn$，最后面的是 $maxn$，你二分的长度是 $mid$，那就是要 $maxn-minn>=mid+1$。
（因为你一个数是由原来的两个数相减得来，所以你 $mid$ 要加一，就像输出答案的一样）

然后最后输出的时候记得判断长度是否大于 $5$，就没什么了。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

int n, now, lst, r[20001], m;
int box[20001], sa[20001], rank[20001];
int fir[20001], kind, ynum, xx[20001], yy[20001];
int height[20001];

void sort_(int m, int *x, int *y) {//基数排序
	for (int i = 1; i <= m; i++)
		box[i] = 0;
	for (int i = 1; i <= n; i++)
		box[x[i]]++;
	for (int i = 2; i <= m; i++)
		box[i] += box[i - 1];
	for (int i = n; i >= 1; i--)
		sa[box[fir[i]]--] = y[i];
}

void SA(int *r, int *sa, int n, int m) {//SA求后缀排名
	int *x = xx, *y = yy; 
	for (int i = 1; i <= n; i++)
		x[i] = fir[i] = r[i];
	for (int i = 1; i <= n; i++)
		y[i] = i;
	for (int i = 1; i <= n; i++)
		fir[i] = x[y[i]];
	sort_(m, x, y);
	
	for (int j = 1; ; j <<= 1) {
		m = kind;
		
		ynum = 0;
		for (int i = n - j + 1; i <= n; i++)
			y[++ynum] = i;
		for (int i = 1; i <= n; i++)
			if (sa[i] > j) y[++ynum] = sa[i] - j;
		
		for (int i = 1; i <= n; i++)
			fir[i] = x[y[i]];
		
		sort_(m, x, y);
		
		swap(x, y);
		kind = 1;
		x[sa[1]] = 1; 
		for (int i = 2; i <= n; i++) {
			if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j])
				x[sa[i]] = kind;
			else x[sa[i]] = ++kind;
		}
		
		if (kind == n) break;
	}
}

void get_height(int *r, int *sa, int n) {//求出SA的height
	int k = 0, j;
	for (int i = 1; i <= n; i++) rank[sa[i]] = i;
	for (int i = 1; i <= n; i++) {
		if (k) k--;
		j = sa[rank[i] - 1];
		while (r[i + k] == r[j + k]) {
			k++;
		}
		height[rank[i]] = k;
	}
}

bool ck(int mid) {//判断能不能找到这么长的长度
	int maxn = sa[1], minn = sa[1];
	for (int i = 2; i <= n; i++) {
		if (height[i] < mid) {//断开
			maxn = sa[i];
			minn = sa[i];
		}
		else {
			maxn = max(maxn, sa[i]);
			minn = min(minn, sa[i]);
			if (maxn - minn >= mid + 1) return 1;//看是否不相交
		}
	}
	
	return 0;
}

void csh() {
	lst = 0;
}

int main() {
	scanf("%d", &n);
//	while (n) {
//		csh();
		
		for (int i = 1; i <= n; i++) {
			scanf("%d", &now);
			r[i] = now - lst + 100;
			lst = now;
		}
		
		SA(r, sa, n, 200);
		
		get_height(r, sa, n);
		
		int lef = 1, rig = n / 2, mid, ans = -1;//二分
		while (lef <= rig) {
			mid = (lef + rig) >> 1;
			if (ck(mid)) {
				ans = mid;
				lef = mid + 1;
			}
			else rig = mid - 1;
		}
		
		if (ans == -1 || ans + 1 < 5) printf("0\n");
			else printf("%d\n", ans + 1);//记得加一
		
//		scanf("%d", &n);
//	}
	
	return 0;
}