求最长不重叠子串

/*
给定一个钢琴的音普序列[值的范围是(1~88)],现在要求找到一个子序列满足
1，长度至少为5
2，序列可以转调，即存在两个子序列，满足一个子序列加/减一个数后可以得到另一个序列
3，两个序列不能有相交的部分。
题意简单来说就是找最长不重叠的重复子串 
*/

#define ll long long
const int maxn = 2e4+5;

/*
-待排序数组长度为 n，放在 0~n-1,在最后加一个‘$‘,让其比所有的字符串中的字符都小，
这样既可以满足字典序的要求，也不越界
*build_sa( ,n+1, );//注意是n+1;
*getheight(,n);
*例如：
*n   = 8;
*num[]   = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0
*rank[]  = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值
*sa[]    = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值
*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值
*/

int n; 
int a[maxn], s[maxn];
int sa[maxn], rank[maxn], height[maxn];
int t1[maxn], t2[maxn], c[maxn];

bool cmp(int *r, int a, int b, int l){
    return r[a] == r[b] && r[a+l] == r[b+l]; // !!!
}

void build_sa(int n, int m){ //m代表估计数字，是ASCll的最大值
    int *x = t1, *y = t2;
    
    for(int i = 0; i < m; i++) c[i] = 0;
    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 j = 1; j <= n; j <<= 1){  // !!!
        int p = 0;
        for(int i = n-j; i < n; i++) y[p++] = i;
        for(int i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i]-j;
        
        for(int i = 0; i < m; i++) c[i] = 0;
        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]] = cmp(y, sa[i-1], sa[i], j)?p-1:p++;
       
        if (p >= n) break;
        m = p; // 下次基数排序的最大值
    }
}

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


bool check(int k){
    int Max = sa[1], Min = sa[1];
    
    for(int i = 2; i <= n; i++){
        if (height[i] < k) Max = Min = sa[i];
        else {
            if (sa[i] < Min) Min = sa[i];
            if (sa[i] > Max) Max = sa[i];
            if (Max - Min >= k) return  true;
        }
    }
    return false;
}
    
int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    while(~scanf("%d", &n) && n){
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]); 
        }
        for(int i = 1; i < n; i++){
            s[i-1] = a[i]-a[i-1]+90;
        }
        n--; // 减少一个单位长度
        s[n] = 0;
        build_sa(n+1, 200); //此时的n是要算上最末尾的特殊字符
        getheight(); //此时的n是不算特殊字符的长度
        
        int l = 1, r = n;
        int ans = -1;
        while(l <= r){
            int mid = (l+r)>>1;
            if (check(mid)){
                ans = mid;
                l = mid+1;
            }
            else r = mid-1;
        }
        if (ans < 4) printf("0\n");
        else printf("%d\n", ans+1); // 这里再加 1 是因为，此串是转换成相邻两差的形式
                                    // 因此要还原最原始的串，则需要长度 +1
    }    
    return 0;
}