L2-008. 最长对称子串

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定"Is PAT&TAP symmetric?"，最长对称子串为"s PAT&TAP s"，于是你应该输出11。

输入格式：

输入在一行中给出长度不超过1000的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

输入样例：

Is PAT&TAP symmetric?

输出样例：

11

manahcer算法讲解转载： http://www.cnblogs.com/biyeymyhjob/archive/2012/10/04/2711527.html

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char s1[2005];
int len1,p[2005]={0};
void manacher(char *s)
{
    int mx=0,id=0;
    int i;
    for(i=1;i<len1;i++)
    {
        if(i<mx)
        {
            p[i]=min(p[2*id-i],mx-i);
        }else
        {
            p[i]=1;
        }
        while(s[i-p[i]]==s[i+p[i]])
            p[i]++;
        if(p[i]+i>mx)
        {
            mx=p[i]+i;
            id=i;
        }
    }
    int mxlen=0;
    for(i=1;i<len1;i++)
    {
        if(mxlen<=p[i])
        {
            mxlen=p[i];
        }
    }
    printf("%d\n",mxlen-1);
}
int main()
{
    char s[1005];
    gets(s);
    int len=strlen(s);
    int i,j;
    s1[0]='$';
    s1[1]='#';
    for(i=0,j=2;i<len;i++,j++)
    {
        s1[j++]=s[i];
        s1[j]='#';
    }
    len1=strlen(s1);
    manacher(s1);
    return 0;
}