HDU 5371 Hotaru's problem Manacher+尺取法

题意：给你一个序列，求最长的两段回文子串，要求他们共用中间的一半。

思路：利用Manacher求出p[i]表示的当前位置的最长回文串长度，然后把每一个长度大于等于2的回文串的左区间和右区间分别放到两个数组里面，由于做manacher时添加了特殊的数字，所以处理的时候稍微注意一下。

　　然后把左右区间按照左端点排序，接着根据尺取法来找答案中的那一段重合的部分。对于每一段右区间R[i]而言，只有L[j].right<=R[i].right && L[j].left<=R[i].right 就是有效的，对于这样的情况所得到的有效值就是L[j].right-R[i].left+1，当然，当L[j].left>R[i].right时，就不能够再处理R[i]了，而是去处理R[i+1]。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #define LL long long
 5 #define MAXN 100005
 6 using namespace std;
 7 int n;
 8 LL s[MAXN * 3];
 9 int p[MAXN];
10 int f[MAXN];
11 int m;
12 struct Node{
13     int left, right;
14     int mm;
15     Node(int left = 0, int right = 0):left(left), right(right){
16         mm = right - left + 1;
17     };
18     bool operator < (const Node & b) const{
19         return left < b.left;
20     }
21 };
22 vector<Node> L, R;
23 void manacher(){
24     int res = 0, id = 0;
25     for(int i = 1; i <= m; i++) {
26         if(res > i){
27             p[i] = min(p[2 * id - i], res - i);
28         }
29         else{
30             p[i] = 1;
31         }
32         //p[i] = mx > i? min(mp[2*id-i], mx-i): 1;
33         while(s[i + p[i]] == s[i - p[i]]){
34             p[i]++;
35         }
36         //while(s[i+mp[i]] == s[i-mp[i]]) mp[i]++;
37         if(i + p[i] > res) {
38             res = i + p[i];
39             id = i;
40         }
41     }
42 }
43 int main()
44 {
45 #ifndef ONLINE_JUDGE
46     freopen("in.txt", "r", stdin);
47     //freopen("out.txt", "w", stdout);
48 #endif // OPEN_FILE
49     int T;
50     scanf("%d", &T);
51     int cas = 1;
52     while(T--){
53         scanf("%d", &n);
54        // char ch;
55         m = 1;
56         s[m++] = -2;
57         s[m++] = -1;
58         //LL x;
59         for(int i = 0; i < n; i++){
60             scanf("%I64d", &s[m++]);
61             s[m++] = -1;
62         }
63         s[m++] = -2;
64         m--;
65         manacher();
66         L.clear();
67         R.clear();
68         for(int i = 4; i <= m; i += 2){
69             if(s[i] != -1 || p[i] == 1) continue;
70             int x = (i / 2) - 1;
71             int y = x - ((p[i] - 1) / 2) + 1;
72             L.push_back(Node(y, x));
73             x++;
74             y = x + ((p[i] - 1) / 2) - 1;
75             R.push_back(Node(x, y));
76             //printf("%d ", p[i] -1);
77         }
78         sort(L.begin(), L.end());
79         sort(R.begin(), R.end());
80         /*for(int i = 0; i < R.size(); i++){
81             printf("%d %d
", R[i].left, R[i].right);
82         }*/
83         int t = 0;
84         int ans = 0;
85         for(int i = 0; i < R.size(); i++){
86             while(t < L.size() && L[t].left <= R[i].left){
87                 if(R[i].left <= L[t].right && L[t].right <= R[i].right){
88                     ans = max(ans, L[t].right - R[i].left + 1);
89                 }
90                 t++;
91             }
92         }
93         printf("Case #%d: %d
", cas++, ans * 3);
94     }
95 }