题目链接:
题目描述：
给出一串数字(数字区间在[1,88])，要在这串数字中找出一个主题，满足：
1：主题长度大于等于5.
2：主题在文本串中重复出现(或者经过调转出现，调转是主题同时加上或者减去同一个整数)
3：重复主题不能重叠
解题思路:
求调转重复出现的子串，那么主题之间的差值一定是不变的。可以求文本串s中相邻两个数的差值，重新组成一个新的文本串S，然后找S后缀串中最长公共不重叠前缀。rank相邻的后缀串，公共前缀一定最长，但是有可能重叠。我们可以二分主题的长度k，然后验证k是否成立。根据height的性质可知，越相似的后缀串rank相差越小，那么我们可以在height[rank]>=k的相邻区间中，找到i=min(sa[rank]),j=max(sa[rank]),如果j-i>=k.则k成立。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 const int maxn = 20010; 8 9 int sa[maxn], rank[maxn], height[maxn]; 10 int t1[maxn], t2[maxn], r[maxn], c[maxn]; 11 bool cmp (int *str, int a, int b, int k) 12 { 13 return str[a]==str[b] && str[a+k]==str[b+k]; 14 } 15 void da (int *str, int n, int m) 16 { 17 n ++; 18 int *x = t1, *y = t2, i, j; 19 for (i=0; i<m; i++) c[i] = 0; 20 for (i=0; i<n; i++) c[x[i]=str[i]] ++; 21 for (i=1; i<m; i++) c[i] += c[i-1]; 22 for (i=n-1; i>=0; i--) sa[-- c[x[i]]] = i; 23 for (j=1; j<=n; j*=2) 24 { 25 int p = 0; 26 for (i=n-j; i<n; i++) y[p++] = i; 27 for (i=0; i<n; i++) if (sa[i] >= j) y[p++] = sa[i] - j; 28 29 for (i=0; i<m; i++) c[i] = 0; 30 for (i=0; i<n; i++) c[x[y[i]]] ++; 31 for (i=1; i<m; i++) c[i] += c[i-1]; 32 for (i=n-1; i>=0; i--) sa[-- c[x[y[i]]]] = y[i]; 33 34 swap (x, y); 35 p = 1; 36 x[sa[0]] = 0; 37 for (int i=1; i<n; i++)//i是rank 38 x[sa[i]] = cmp(y, sa[i-1], sa[i], j)?p-1:p++; 39 if (p >= n) 40 break; 41 m = p; 42 } 43 for (i=1; i<n; i++) 44 rank[sa[i]] = i; 45 int k = 0; 46 n --; 47 for (int i=0; i<n; i++) 48 { 49 if (k) k --; 50 int j = sa[rank[i] - 1]; 51 while (str[i+k] == str[j+k]) k++; 52 height[rank[i]] = k; 53 } 54 } 55 bool solve (int x, int n) 56 { 57 int ma, mi; 58 ma = mi = sa[1]; 59 for (int i=2; i<=n; i++) 60 { 61 if (height[i]>=x && i<=n) 62 { 63 mi = min(mi, sa[i]); 64 ma = max(ma, sa[i]); 65 if (ma - mi >= x) return true; 66 continue; 67 } 68 69 ma = mi = sa[i]; 70 } 71 return false; 72 } 73 int main () 74 { 75 int n; 76 while (scanf ("%d", &n), n) 77 { 78 int s, e; 79 scanf ("%d", &s); 80 for (int i=1; i<n; i++) 81 { 82 scanf ("%d", &e); 83 r[i-1] = s - e + 100; 84 s = e; 85 } 86 r[--n] = 0; 87 88 da (r, n, 200); 89 int ans = 0, high = n / 2, low = 1, mid; 90 while (low <= high) 91 { 92 mid = (low + high) / 2; 93 if (solve (mid, n)) 94 { 95 ans = mid; 96 low = mid + 1; 97 } 98 else 99 high = mid - 1; 100 } 101 printf ("%d ", ans<4 ? 0:ans+1); 102 } 103 return 0; 104 }