题意：给你一个序列，求最长的两段回文子串，要求他们共用中间的一半。
思路：利用Manacher求出p【i】表示的当前位置的最长回文串长度，然后把每一个长度大于等于2的回文串的左区间和右区间分别放到两个数组里面，由于做manacher时添加了特殊的数字，所以处理的时候稍微注意一下。
然后把左右区间按照左端点排序，接着根据尺取法来找答案中的那一段重合的部分。对于每一段右区间R【i】而言，只有L【j】.right<=R【i】.right && L【j】.leftR【i】.right时，就不能够再处理R【i】了，而是去处理R【i+1】。
1 #include
2 #include
3 #include
4 #define LL long long
5 #define MAXN 100005
6 using namespace std;
7 int n;
8 LL s【MAXN 3】;
9 int //代码效果参考：http://www.lyjsj.net.cn/wz/art_22988.html
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 [span style="color: rgba(0, 0, 0, 1)"> b.left;
20 }
21 };
22 vector 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【2id-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 //代码效果参考：http://www.lyjsj.net.cn/wx/art_22986.html
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\n", R【i】.left, R【i】.right);
82 }/
83 int t //代码效果参考：http://www.lyjsj.net.cn/wz/art_22984.html
= 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\n", cas++, ans 3);
94 }
95 }
