- #include<cstdio>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- const int MAX = 20025;
- int num[MAX];
- int sa[MAX], rank[MAX], height[MAX];
- int wa[MAX], wb[MAX], wv[MAX], wd[MAX];
- int N;
- int cmp(int *r, int a, int b, int l)
- {
- return r[a] == r[b] && r[a+l] == r[b+l];
- }
- void Getsa(int *r, int n, int m)
- {
- int i, j, p, *x = wa, *y = wb, *t;
- for(i = 0; i < m; i ++) wd[i] = 0;
- for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++;
- for(i = 1; i < m; i ++) wd[i] += wd[i-1];
- for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i;
- for(j = 1, p = 1; p < n; j *= 2, m = p)
- {
- for(p = 0, 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 ++) wd[i] = 0;
- for(i = 0; i < n; i ++) wd[wv[i]] ++;
- for(i = 1; i < m; i ++) wd[i] += wd[i-1];
- for(i = n-1; i >= 0; i --) sa[-- wd[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 GetHeight(int *r, int n) // ?height???
- {
- 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 ++);
- }
- }
- bool AC(int k)
- {
- int l=1,mx,mn,r;
- while (l<=N)
- {
- r=l;
- mx=mn=sa[l];
- while (height[r+1]>=k && r<N)
- {
- r++;
- if (mx<sa[r]) mx=sa[r];
- if (mn>sa[r]) mn=sa[r];
- }
- if (mx-mn>k) return true;
- l=r+1;
- }
- return false;
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- while (scanf("%d",&N)!=EOF)
- {
- int i;
- if (N==0) return 0;
- for ( i=0;i<N;i++) scanf("%d",&num[i]);
- if (N<10)
- {
- printf("0\\n");
- continue;
- }
- for ( i=0;i<N-1;i++) num[i]=num[i+1]-num[i]+100;
- N--;
- num[N] = 0;
- Getsa(num, N + 1, 200);
- GetHeight(num, N);
- int l=1,r=N,mid;
- while (l+1<r)
- {
- mid=(l+r)>>1;
- if (AC(mid)) l=mid;
- else r=mid;
- }
- if (l<4) printf("0\\n");
- else printf("%d\\n",l+1);
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/251120137476.html
来源: http://www.codesnippet.cn/detail/251120137476.html