1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
const int MAXN = 20010;
6
int buc[MAXN], wa[MAXN], wb[MAXN], n;
7
int r[MAXN], sa[MAXN], Rank[MAXN], height[MAXN];
8
void getheight(int n)
9
{
10
    int i, j, k = 0;
11
    for (i = 0; i < n; i++)
12
        Rank[sa[i]] = i;
13
    for (i = 0; i < n; height[Rank[i++]] = k)
14
        for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++)
15
            ;
16
    return;
17
}
18
bool cmp(int *c, int a, int b, int d)
19
{
20
    return c[a] == c[b] && c[a + d] == c[b + d];
21
}
22
void da(int n, int m = 320)
23
{
24
    // for(int i=0;i<n;i++)printf("%d  %d\n",i,r[i]);
25
    int i, j, p, *x = wa, *y = wb, *t;
26
    for (i = 0; i < m; i++)
27
        buc[i] = 0;
28
    for (i = 0; i < n; i++)
29
        buc[x[i] = r[i]]++;
30
    for (i = 1; i < m; i++)
31
        buc[i] += buc[i - 1];
32
    for (i = n - 1; ~i; i--)
33
        sa[--buc[x[i]]] = i;
34
    for (j = 1, p = 1; p < n; j *= 2, m = p)
35
    {
36
        for (i = n - j, p = 0; i < n; i++)
37
            y[p++] = i;
38
        for (i = 0; i < n; i++)
39
            if (sa[i] >= j)
40
                y[p++] = sa[i] - j;
41
        for (i = 0; i < m; i++)
42
            buc[i] = 0;
43
        for (i = 0; i < n; i++)
44
            buc[x[y[i]]]++;
45
        for (i = 1; i < m; i++)
46
            buc[i] += buc[i - 1];
47
        for (i = n - 1; ~i; i--)
48
            sa[--buc[x[y[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
    // for(int i=0;i<n;i++)
53
    //     printf("%d  %d\n",i,sa[i]);
54
    getheight(n);
55
    return;
56
}
57
bool Judge(int mid)
58
{
59
    int Min = 0x3f3f3f3f, Max = -0x3f3f3f3f;
60
    for (int i = 2; i <= n; i++)
61
    {
62
        if (height[i] < mid)
63
            Min = 0x3f3f3f3f, Max = -0x3f3f3f3f;
64
        else
65
        {
66
            Min = min(Min, min(sa[i - 1], sa[i]));
67
            Max = max(Max, max(sa[i - 1], sa[i]));
68
            if (Max - Min > mid)
69
                return 1;
70
        }
71
    }
72
    return 0;
73
}
74
int a[MAXN];
75
int main()
76
{
77
    while (~scanf("%d", &n) && n)
78
    {
79
        for (int i = 0; i < n; i++)
80
            scanf("%d", &a[i]);
81
        n--;
82
        for (int i = 0; i < n; i++)
83
            r[i] = a[i + 1] - a[i] + 88;
84
        r[n] = 0;
85
        da(n + 1);
86
        int l = 0, r = (n >> 1) + 1, ans = 0;
87
        while (l < r)
88
        {
89
            int m = l + r >> 1;
90
            if(Judge(m))
91
                ans = m, l = m + 1;
92
            else
93
                r = m;
94
        }
95
        if (ans >= 4) printf("%d\n", ans + 1);
96
        else printf("0\n");
97
    }
98
}

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int MAXN = 2000005;
6
int buc[MAXN], wa[MAXN], wb[MAXN], n, K;
7
int r[MAXN], sa[MAXN], Rank[MAXN], height[MAXN];
8
void GetHeight(int n)
9
{
10
    int i, j, k = 0;
11
    for (i = 0; i < n; i++)
12
        Rank[sa[i]] = i;
13
    for (i = 0; i < n; height[Rank[i++]] = k)
14
        for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++)
15
            ;
16
    return;
17
}
18
bool cmp(int *c, int a, int b, int d)
19
{
20
    return c[a] == c[b] && c[a + d] == c[b + d];
21
}
22
void da(int n, int m = 1000000)
23
{
24
    int i, j, p, *x = wa, *y = wb, *t;
25
    for (i = 0; i < m; i++)
26
        buc[i] = 0;
27
    for (i = 0; i < n; i++)
28
        buc[x[i] = r[i]]++;
29
    for (i = 1; i < m; i++)
30
        buc[i] += buc[i - 1];
31
    for (i = n - 1; ~i; i--)
32
        sa[--buc[x[i]]] = i;
33
    for (j = 1, p = 1; p < n; j *= 2, m = p)
34
    {
35
        for (i = n - j, p = 0; i < n; i++)
36
            y[p++] = i;
37
        for (i = 0; i < n; i++)
38
            if (sa[i] >= j)
39
                y[p++] = sa[i] - j;
40
        for (i = 0; i < m; i++)
41
            buc[i] = 0;
42
        for (i = 0; i < n; i++)
43
            buc[x[y[i]]]++;
44
        for (i = 1; i < m; i++)
45
            buc[i] += buc[i - 1];
46
        for (i = n - 1; ~i; i--)
47
            sa[--buc[x[y[i]]]] = y[i];
48
        for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
49
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
50
    }
51
    GetHeight(n);
52
    return;
53
}
54
bool Judge(int mid)
55
{
56
    int l = 0;
57
    for (int i = 2; i <= n; i++)
58
    {
59
        if (height[i] < mid)
60
            l = 0;
61
        else
62
        {
63
            l++;
64
            if(l + 1 >= K) return 1;
65
        }
66
    }
67
    return 0;
68
}
69
int main()
70
{
71
    scanf("%d%d", &n, &K);
72
    for (int i = 0; i < n; i++)
73
        scanf("%d", &r[i]);
74
    da(n + 1);
75
    int l = 0, r = (n >> 1) + 1, ans = 0;
76
    while (l < r)
77
    {
78
        int mid = l + r >> 1;
79
        if (Judge(mid))
80
            ans = mid, l = mid + 1;
81
        else
82
            r = mid;
83
    }
84
    printf("%d", ans);
85
}