字符串：HDU5371-Hotaru's problem（manacher 的应用）

Hotaru’s problem

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Hotaru Ichijou recently is addicated to math problems. Now she is playing with N-sequence.
Let’s define N-sequence, which is composed with three parts and satisfied with the following condition:
1. the first part is the same as the thrid part,
2. the first part and the second part are symmetrical.
for example, the sequence 2,3,4,4,3,2,2,3,4 is a N-sequence, which the first part 2,3,4 is the same as the thrid part 2,3,4, the first part 2,3,4 and the second part 4,3,2 are symmetrical.

Give you n positive intergers, your task is to find the largest continuous sub-sequence, which is N-sequence.

Input

There are multiple test cases. The first line of input contains an integer T（T<=20）, indicating the number of test cases.

For each test case:

the first line of input contains a positive integer N（1<=N<=100000）, the length of a given sequence

the second line includes N non-negative integers ,each interger is no larger than 109 , descripting a sequence.

Output

Each case contains only one line. Each line should start with “Case #i: ”,with i implying the case number, followed by a integer, the largest length of N-sequence.

We guarantee that the sum of all answers is less than 800000.

Sample Input

1
10
2 3 4 4 3 2 2 3 4 4

Sample Output

Case #1: 9

---

解题心得：

1. 就是manacher的应用，要求的是两个回文串，左方回文串左半和右方回文串右半相重合。所以要使用manacher求出以每个数字为对称轴的半径。然后在判断是否两个回文串符合要求。
2. 关于判断重和部分，先找到一个对称轴然后每次从ans（之取最大值）到当前部分对称半径枚举，找到右半部份的对称中心（左半部分的对称轴+左半部分的对称半径），如果右半部份的对称半径符合要求则改变ans（因为是从ans开始，所以得到的答案肯定大于ans）。

---

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+100;
int num[maxn],rl[maxn];

//manacher模板
void manacher(int tot)
{
    int max_right = 0,pos = 0;
    for(int i=0;i<tot;i++)
    {
        if(i < max_right)
            rl[i] = min(rl[pos*2-i],max_right-i);
        else
            rl[i] = 1;
        while(i-rl[i]>=0 && i+rl[i]<tot && num[i+rl[i]] == num[i-rl[i]])
            rl[i]++;//找到以每个数字为对称中心的对称半径
        if(i+rl[i]-1 > max_right)
        {
           max_right = i+rl[i]-1;
           pos = i;
        }
    }
}

int main()
{
    int t,T;
    scanf("%d",&t);
    T = t;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int tot = 0;
        for(int i=0;i<n;i++)
        {
            int now;
            scanf("%d",&now);
            num[tot++] = -1;
            num[tot++] = now;
        }
        num[tot++] = -1;
        manacher(tot);
        int ans = 1;
        for(int i=0;i<tot;i+=2)//从题目可以看出肯定是偶数长度的回文串
        {
            for(int j=ans;j<=rl[i];j+=2)
                if(rl[i+j-1]>=j)//左右半径可以相互重合
                    ans = j;
        }
        printf("Case #%d: %d
",T-t,ans/2*3);//ans/2*3的出的才是两个符合要求的回文串的长度
    }
}