【题意】：求一个字符串的不可重叠最长重复子串。

【题解】：后缀数组经典题目。
              先二分答案，把题目变成判定性问题：判断是否存在两个长度为k 的子串是相同的，且不重叠。解决这个问题的关键是利用height 数组，把排序后的后缀分成若干组，其中每组的后缀之间的height值都不小于k。
              容易看出，有希望成为最长公共前缀不小于k 的两个后缀一定在同一组。然后对于每组后缀，只须判断每个后缀的sa 值的最大值和最小值之差是否不小于k。如果有一组满足，则说明存在，否则不存在。时间复杂度为O(nlogn)。

【代码】：
  1 #include "iostream"
  2 #include "cstdio"
  3 #include "cstring"
  4 #include "algorithm"
  5 #include "vector"
  6 #include "queue"
  7 #include "cmath"
  8 #include "string"
  9 #include "cctype"
 10 #include "map"
 11 #include "iomanip"
 12 #include "set"
 13 #include "utility"
 14 using namespace std;
 15 typedef pair<int, int> pii;
 16 #define pb push_back
 17 #define mp make_pair
 18 #define fi first
 19 #define se second
 20 #define sof(x) sizeof(x)
 21 #define lc(x) (x << 1)
 22 #define rc(x) (x << 1 | 1)
 23 #define lowbit(x) (x & (-x))
 24 #define ll long long
 25 #define maxn 20050
 26 int wa[maxn], wb[maxn], wv[maxn], wc[maxn];
 27 int r[maxn], sa[maxn], rank[maxn], height[maxn];
 28 int n;
 29 
 30 int cmp(int *r, int a, int b, int l) {
 31     return r[a] == r[b] && r[a+l] == r[b+l];
 32 }
 33 
 34 void da() {
 35     //m为最大字符
 36     int i, j, p, *x = wa, *y = wb, *t, m = 256;
 37     for(i = 0; i < m; i++) wc[i] = 0;
 38     for(i = 0; i <= n; i++) wc[x[i] = r[i]]++;
 39     for(i = 1; i < m; i++) wc[i] += wc[i-1];
 40     for(i = n; i >= 0; i--) sa[--wc[x[i]]] = i;
 41     for(j = 1, p = 1; p < n; j *= 2, m = p) {
 42         for(p = 0, i = n - j + 1; i <= n; i++) y[p++] = i;
 43         for(i = 0; i <= n; i++) if(sa[i] >= j) y[p++] = sa[i] - j;
 44         for(i = 0; i <= n; i++) wv[i] = x[y[i]];
 45         for(i = 0; i < m; i++) wc[i] = 0;
 46         for(i = 0; i <= n; i++) wc[wv[i]]++;
 47         for(i = 1; i < m; i++) wc[i] += wc[i-1];
 48         for(i = n; i >= 0; i--) sa[--wc[wv[i]]] = y[i];
 49         for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i <= n; i++)
 50             x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1 : p++;
 51     }
 52 }
 53 
 54 void calheight() {
 55     int i, j, k = 0;
 56     for(i = 1; i <= n; i++) rank[sa[i]] = i;
 57     for(i = 0; i < n; height[rank[i++]] = k)
 58         for(k ? k-- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);
 59 }
 60 
 61 bool check(int mid) {
 62     int minn = sa[1], maxx = sa[1];
 63     for(int i = 2; i <= n; i++) {
 64         if(height[i] >= mid) {
 65             minn = min(minn, sa[i]);
 66             maxx = max(maxx, sa[i]);
 67             if(maxx - minn >= mid) return 1;
 68         } else minn = maxx = sa[i];
 69     }
 70     return false;
 71 }
 72 
 73 void solve() {
 74     da();//求sa数组
 75     calheight();//求rank数组和height数组
 76     int l = 1, r = n, ans = -1;
 77     while(l <= r) {
 78         int mid = (l + r) >> 1;
 79         if(check(mid)) ans = mid, l = mid + 1;
 80         else r = mid - 1;
 81     }
 82     if(ans >= 4) printf("%d\n", ans + 1);
 83     else printf("0\n");
 84 }
 85 
 86 int main() {
 87     int a, b;
 88     while(~scanf("%d", &n)) {
 89         if(!n) break;
 90         n--;
 91         scanf("%d", &b);
 92         for(int i = 0; i < n; i++) {
 93             scanf("%d", &a);
 94             r[i] = a - b + 100;
 95             b = a;
 96         }
 97         r[n] = 0;
 98         solve();
 99     }
100     return 0;
101 }
102