HDU3068 最长回文串

题目大意：给出一个字符串，求其回文串的长度。有多组数据。

分析：manacher算法模板题。

//在原字符串两边和中间插入一个从未出现的字符，比如‘#’。然后再在最前面插入一个‘*’。
#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MAXN 230005

char s1[MAXN],s2[MAXN];

int ans,p[MAXN],maxid,len;

int main()

{

    while(scanf("%s",s1)!=-)

    {

        ans=;

        memset(p,,sizeof p);

        memset(s2,,sizeof s2);

        len=strlen(s1);

        s2[]='*';

        s2[]='#';

        for(int i=,j=;i<len;i++)

        {

            s2[j++]=s1[i];

            s2[j++]='#';

        }

        len=strlen(s2);

        p[]=,maxid=;

        for(int i=;i<len;i++)

        {

            if(p[maxid]+maxid>i)

            {

               p[i]=min(p[*maxid-i],maxid+p[maxid]-i);

            }

            else p[i]=;

            for(;i+p[i]<len&&i-p[i]>=&&s2[i+p[i]]==s2[i-p[i]];p[i]++)

            if(p[i]+i>p[maxid]+maxid)maxid=i;

        }

        for(int i=;i<len;i++)

            if(p[i]>ans)ans=p[i];

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

    }

}