hdu 4513 吉哥系列故事——完美隊形II Manacher變形

傳送門：吉哥系列故事——完美隊形II

馬拉車的簡單變形，如果不懂Manacher算法請移步：Manacher算法講解

AC CODE

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MX = e5 + ;
int A[MX];
int ma[MX<<];
int p[MX<<];

void Manacher(int n)
{
    int l = ;
    ma[l++] = -;
    ma[l++] = ;
    for(int i=;i<n;i++) {
        ma[l++] = A[i];
        ma[l++] = ;
    }
    ma[l] = -;p[] = ;
    int mx = ,id = ;
    for(int i=;i<=l;i++) {
        p[i] = mx>i ? min(p[*id-i],mx-i) : ;
        while(ma[i+p[i]] == ma[i-p[i]] && ma[i-p[i]]<=ma[i-p[i]+]) p[i]++;
        if(i+p[i]>mx) {
            mx = i+p[i];
            id = i;
        }
    }

}

int main()
{
    int ,n;//freopen("in.txt","r",stdin);
    scanf("%d",&);
    while(--)
    {
        scanf("%d",&n);
        for(int i=;i<n;i++) scanf("%d",&A[i]);
        Manacher(n);
        int ans = ;
        for(int i=;i<=*n+;i++) ans = max(ans,p[i]-);
        printf("%d\n",ans);
    }

    return ;
}