HDU 5371 Manacher Hotaru's problem

求出一個連續子序列，這個子序列由三部分ABC構成，其中AB是回文串，A和C相同，也就是BC也是回文串。

求這樣一個最長的子序列。

Manacher算法是在所有兩個相鄰數字之間插入一個特殊的數字，比如-1，

Manacher算法跑完之后，就計算出每個數字為中心的回文子序列的最大長度

由題意可以知道，AB和BC必然是長度為偶數的回文串。所以我們枚舉回文串的中心就枚舉相鄰兩個數字之間的縫隙，也就是那些-1

把AB中間的間隙叫做左中心i，BC之間的間隙叫做右中心j，那么如果兩個中心的范圍能夠互相覆蓋，那么就找到一個符合條件的連續子序列。

做法就是枚舉左中心i，在左中心的范圍內枚舉右中心j，然后維護一個最大值即可。

在枚舉j的時候不要直接從[i+1, i + p[i] - 1]枚舉，會超時的。

比如說我們維護的最大值是ans，那么直接從 i + ans 開始枚舉，因為之前的區間即使找到合法子序列也并不能更新這個最大值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100000 + 10;

int n, tot;
int a[maxn], b[maxn * 2];

int p[maxn * 2];

void Manacher()
{
    int id, mx = 0;
    p[0] = 0;
    for(int i = 1; i < tot; i++)
    {
        if(mx > i) p[i] = min(p[id * 2 - i], mx - i);
        else p[i] = 1;
        while(b[i + p[i]] == b[i - p[i]]) p[i]++;
        if(i + p[i] > mx) { mx = i + p[i]; id = i; }
    }
}

int main()
{
    int T; scanf("%d", &T);
    for(int kase = 1; kase <= T; kase++)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%d", a + i);

        b[0] = -2, b[1] = -1;
        tot = 2;
        for(int i = 0; i < n; i++)
        {
            b[tot++] = a[i];
            b[tot++] = -1;
        }

        Manacher();

        int ans = 1;
        for(int i = 3; i < tot; i += 2)
        {
            for(int j = ans; j <= p[i]; j += 2)
                if(p[i + j - 1] >= j) ans = j;
        }

        ans = ans / 2 * 3;
        printf("Case #%d: %d\n", kase, ans);
    }

    return 0;
}

?