二分长度k 长度大于等于k的分成一组 每组sa最大的和最小的距离大于k 说明可行
#include#include #include using namespace std;const int maxn = 20010;int s[maxn];int sa[maxn];int t[maxn], t2[maxn], c[maxn];int rank[maxn], height[maxn];void build_sa(int m, int n){ int i, *x = t, *y = t2; for(i = 0; i < m; i++) c[i] = 0; for(i = 0; i < n; i++) c[x[i] = s[i]]++; for(i = 1; i < m; i++) c[i] += c[i-1]; for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i; for(int k = 1; k <= n; k <<= 1) { int p = 0; for(i = n-k; i < n; i++) y[p++] = i; for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k; for(i = 0; i < m; i++) c[i] = 0; for(i = 0; i < n; i++) c[x[y[i]]]++; for(i = 0; i < m; i++) c[i]+= c[i-1]; for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; swap(x, y); p = 1; x[sa[0]] = 0; for(i = 1; i < n; i++) x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k] ? p-1 : p++; if(p >= n) break; m = p; }}void getHeight(int n){ 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 ok(int n, int k){ int ans1 = sa[1], ans2 = sa[1]; for(int i = 2; i <= n; i++) { if(height[i] < k) { ans1 = ans2 = sa[i]; } else { ans1 = max(ans1, sa[i]); ans2 = min(ans2, sa[i]); if(ans1-ans2 > k) return true; } } return false;}int main(){ int n; while(scanf("%d", &n) && n) { for(int i = 0; i < n; i++) scanf("%d", &s[i]); n--; for(int i = 0; i < n; i++) s[i] = s[i+1] - s[i] + 90; s[n] = 0; build_sa(200, n+1); getHeight(n); int l = 4, r = n+1; int ans = -1; while(l <= r) { int m = (l+r) >> 1; if(ok(n, m)) { l = m+1; ans = m; } else r = m-1; } printf("%d\n", ans+1); } return 0;}