Eva

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 4814  Solved: 1924
Description

输入分为两行，第一行为一个整数

/**************************************************************

    Problem: 2342

    User: ictsing

    Language: C++

    Result: Accepted

    Time:96 ms

    Memory:6660 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

using namespace std;

const int mt=500000+5;

char s[mt],ch[(mt+2)<<1];

int p[(mt+2)<<1];

int ans=0,maxx=0,id=0,n;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void manacher()

{

    for(int i=1;i<=n;i++)

    {

        p[i]=maxx>i?min(p[id*2-i],maxx-i):0;

        while(ch[i-p[i]-1]==ch[i+p[i]+1]) p[i]++;

        if(i+p[i]>maxx) maxx=i+p[i],id=i;

    }

}

int main()

{

    n=read();

    scanf("%s",s+1);

    for(int i=1;i<=n;i++)//

        ch[i*2-1]=s[i],ch[i*2]='#';

     n=n*2+1;ch[n]='@',ch[0]='#';

    manacher();

    for(int i=2;i<=n;i+=2)

    {

        int j=max(0,(i*2-p[i])/2);//

        if(j&1) j++;

        while(j<i&&j+p[j]<i) j+=2;

        if(j<i) ans=max(ans,(i-j)*2);

    }

    printf("%d\n",ans);

}