[Hdu3068]最长回文[Manacher]

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>

using namespace std;

int    p[210000];
char    s[210000];

int main()
{
    while(~scanf("%s",s))
    {
        int    n=strlen(s),pos=0,Max=0;
        for(int i=n;i>=0;--i)
        {
            s[i+i+2]=s[i];
            s[i+i+1]='#';
        }
        s[0]='*';
        for(int i=2;i<=(n<<1|1);++i)
        {
            if(p[pos]+pos>i)
                p[i]=min(p[(pos<<1)-i],p[pos]+pos-i);
            else    p[i]=1;
            while(s[i-p[i]]==s[i+p[i]])++p[i];
            if(pos+p[pos]<i+p[i])pos=i;
            if(Max<p[i])Max=p[i];
        }
        printf("%d
",Max-1);
    }

    return 0;
}