L2-008. 最长对称子串

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

输入格式：

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

输出格式：

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

Is PAT&TAP symmetric?输出样例：
11
解题思路：Manacher算法
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <cmath>#include <queue>#include <vector>#include <set>#include <stack>#include <map>#include <climits>using namespace std;#define LL long longconst int INF=0x3f3f3f3f;char s1[110009],s2[220009];int p[220009];int main(){    while(gets(s1))    {        int i=0,len=1;        s2[0]='$';        while(s1[i]!='/0')        {            s2[len++]='#';            s2[len++]=s1[i];            i++;        }        s2[len++]='#';        s2[len]='/0';        memset(p,0,sizeof p);        int id=0,ma=0;        for(int i=0;i<len;i++)        {            p[i]=ma>i?min(p[id*2-i],ma-i):1;            while(s2[i+p[i]]==s2[i-p[i]]) p[i]++;            if(i+p[i]>ma)            {                ma=i+p[i];                id=i;            }        }        int ans=0;        for(int i=0;i<len;i++)            ans=max(ans,p[i]-1);        PRintf("%d/n",ans);    }    return 0;}