poj1743 后缀数组+二分

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 using namespace std;
  6 #define maxn 20010
  7 int n;
  8 struct node
  9 {
 10     int now, next;
 11 } d[maxn];
 12 int val[maxn][2], c[maxn], Rank[maxn], SA[maxn], pos[maxn], x[maxn];
 13 int h[maxn];
 14 int height[maxn];
 15 void add_value(int u, int v, int i)
 16 {
 17     d[i].next = c[u];
 18     c[u] = i;
 19     d[i].now = v;
 20 }
 21 void radix_sort(int l, int r)
 22 {
 23     for (int k = 1; k >= 0; k--)
 24     {
 25         memset(c, 0, sizeof(c));
 26         for (int i = r; i >= l; i--)
 27             add_value(val[pos[i]][k], pos[i], i);
 28         int t = 0;
 29         for (int i = 0; i <= maxn; i++)
 30         for (int j = c[i]; j; j = d[j].next)pos[++t] = d[j].now;
 31     }
 32     int t = 0;
 33     for (int i = 1; i <= n; i++)
 34     {
 35         if (val[pos[i]][0] != val[pos[i - 1]][0] || val[pos[i]][1] != val[pos[i - 1]][1])t++;
 36         Rank[pos[i]] = t;
 37     }
 38 }
 39 void get_suffix_array()
 40 {
 41     int t = 1;
 42     while (t / 2 <= n)
 43     {
 44         for (int i = 1; i <= n; i++)
 45         {
 46             val[i][0] = Rank[i];
 47             val[i][1] = (((i + t / 2 <= n) ? Rank[i + t / 2] : 0));
 48             pos[i] = i;
 49         }
 50         radix_sort(1, n);
 51         t *= 2;
 52     }
 53     for (int i = 1; i <= n; i++)
 54         SA[Rank[i]] = i;
 55 }
 56 void get_common_prefix()
 57 {
 58     memset(h, 0, sizeof(h));
 59     for (int i = 1; i <= n; i++)
 60     {
 61         if (Rank[i] == 1)h[i] = 0;
 62         else
 63         {
 64             int now = 0;
 65             if (i > 1 && h[i - 1] > 1)now = h[i - 1] - 1;
 66             while (now + i <= n&&now + SA[Rank[i] - 1] <= n&&x[now + i] == x[now + SA[Rank[i] - 1]])
 67                 now++;
 68             h[i] = now;
 69         }
 70     }
 71     for (int i = 1; i <= n; i++)
 72         height[Rank[i]] = h[i];
 73 }
    //之前说按照height的值进行分组，当存在一段连续的height满足条件时，说明这些height在一组里。当有一个height不满足时，这一组结束。则在这一组里找SA相差最大的一对，看是否满足条件
 74 bool exist(int len)
 75 {
 76     
 77     int Min = n + 1, Max = 0;
 78     for (int i = 1; i <= n; i++)
 79     if (height[i] < len)
 80     {
 81         //如果已知的最大与最小值的差值满足条件，直接退出。
 82         if (Max - Min >= len)return 1;
 83         Min = Max = SA[i];
 84     }
 85     else//在条件满足的情况下，使差值最大化
 86     {
 87         Min = min(Min, SA[i]);
 88         Max = max(Max, SA[i]);
 89     }
 90     if (Max - Min >= len)return 1;
 91     return 0;
 92 }
 93 int binary_search(int l, int r)
 94 {
 95     while (l <= r)
 96     {
 97         int mid = (l + r) / 2;
 98         if (exist(mid))l = mid + 1;
 99         else r = mid - 1;
100     }
101     return r;
102 }
103 void solve()
104 {
105     //题目限定
106     for (int i = 1; i <= n - 1; i++)
107         Rank[i] =x[i]= x[i + 1] - x[i] + 88;
108     n--;
109     get_suffix_array();
110     get_common_prefix();
111     int ans = binary_search(0, n) + 1;
112     ans = ((ans<5) ? 0 : ans);
113     printf("%d\n", ans);
114 }
115 int main()
116 {
117     while (scanf("%d\n", &n), n > 0)
118     {
119         for (int i = 1; i <= n; i++)
120             scanf("%d", &x[i]);
121         solve();
122     }
123     return 0;
124 }