Description
Input
Output
题目大意：给N个数字，对着N个数字前后作差得到一段N-1个数字的序列，问重复出现两次且不重叠的子段最长有多长。（看清楚上面的题目噢）
思路：N个数字作差，得到N-1个数字的序列，求后缀数组，二分验证是否存在mid长度的符合要求的字符串。
代码（219MS）：
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 7 const int MAXN = 20010; 8 int s[MAXN]; 9 int n, sa[MAXN], height[MAXN], rank[MAXN], tmp[MAXN], c[MAXN]; 10 11 void makesa(int m) { 12 memset(c, 0, sizeof(c)); 13 for(int i = 0; i < n; ++i) ++c[rank[i] = s[i]]; 14 for(int i = 0; i < m; ++i) c[i] += c[i - 1]; 15 for(int i = 0; i < n; ++i) sa[--c[rank[i]]] = i; 16 for(int k = 1; k < n; k <<= 1) { 17 for(int i = 0; i < n; ++i) { 18 int j = sa[i] - k; 19 if(j < 0) j += n; 20 tmp[c[rank[j]]++] = j; 21 } 22 int j = c[0] = sa[tmp[0]] = 0; 23 for(int i = 1; i < n; ++i) { 24 if(rank[tmp[i]] != rank[tmp[i - 1]] || rank[tmp[i] + k] != rank[tmp[i - 1] + k]) 25 c[++j] = i; 26 sa[tmp[i]] = j; 27 } 28 memcpy(rank, sa, n * sizeof(int)); 29 memcpy(sa, tmp, n * sizeof(int)); 30 if(j >= n - 1) break; 31 } 32 } 33 34 void calheight() { 35 int j, k = 0; 36 for(int i = 0; i < n; height[rank[i++]] = k) { 37 if(k > 0) --k; 38 for(j = sa[rank[i] - 1]; s[i + k] == s[j + k]; ++k); 39 } 40 } 41 42 bool check(int k) { 43 int mx = sa[0], mn = sa[0]; 44 for(int i = 1; i < n; ++i) { 45 if(height[i] >= k - 1) { 46 mx = max(mx, sa[i]); 47 mn = min(mn, sa[i]); 48 } else { 49 if(mx - mn >= k) return true; 50 mx = mn = sa[i]; 51 } 52 } 53 return mx - mn >= k; 54 } 55 56 int solve() { 57 int l = 1, r = n; 58 while(l < r) { 59 int mid = (l + r) >> 1; 60 if(check(mid)) l = mid + 1; 61 else r = mid; 62 } 63 return l - 1; 64 } 65 66 int main() { 67 while(scanf("%d", &n) != EOF && n) { 68 for(int i = 0; i < n; ++i) scanf("%d", &s[i]); 69 for(int i = 0; i < n - 1; ++i) s[i] = s[i + 1] - s[i] + 88; 70 s[n - 1] = 0; 71 makesa(176); 72 if(n != 1) calheight(); 73 int ans = solve(); 74 printf("%d\n", ans >= 5 ? ans : 0); 75 } 76 }
原文：http://www.cnblogs.com/oyking/p/3535183.html
