字符串：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

解题心得：

就是manacher的应用，要求的是两个回文串，左方回文串左半和右方回文串右半相重合。所以要使用manacher求出以每个数字为对称轴的半径。然后在判断是否两个回文串符合要求。
关于判断重和部分，先找到一个对称轴然后每次从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\n",T-t,ans/2*3);//ans/2*3的出的才是两个符合要求的回文串的长度

    }

}

巴特西