hdu4513 [manacher模板题]

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn= 2e5+50;
const int mod=1e9+7;
int a[maxn];
int pal[maxn];
int n;
int manacher()
{
    int max_len=0;
    int mx =0,id =0;
    memset(pal,0,sizeof(pal));
    for(int i=1;i<=n*2;i++)
    {
        if(mx>=i) pal[i] = min(mx-i+1,pal[2*id-i]);
        else pal[i]=1;
        while(a[i-pal[i]]==a[i+pal[i]]&&a[i-pal[i]]<=a[i-pal[i]+2]) pal[i]++;
        if(i+pal[i]-1>mx)
        {
            mx = i+pal[i]-1;
            id=i;
        }
        max_len = max(max_len, pal[i] - 1);
    }
    return max_len;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        //int n;
        scanf("%d",&n);
        a[0]=-1;
        for(int i=1;i<=n;i++)
        {
            a[2*i-1]=0;
            scanf("%d",&a[i*2]);
        }
        a[2*n+1]=0;
        printf("%d\n",manacher());
    }
    return 0;
}