题目链接：点击打开链接
题意：求一个字符串的最长对称字串
题解：Manacher算法，跑一遍，不会Manacher算法的可以看我这篇博客：http://blog.csdn.net/PK__PK/article/details/79566540
代码：
#include <stdio.h> #include <cstring> #include <algorithm> using namespace std; #define MAX 100000 char s[MAX*3]; int p[MAX*3]; int manacher(){ int ans=0,id=0,maxn=0,len=strlen(s); for(int i=len;i>=0;i--){ s[i*2+2]=s[i]; s[i*2+1]='#'; } s[0]='*'; for(int i=1;i<=len*2+1;i++){ if(maxn>i)p[i]=min(p[id*2-i],maxn-i); else p[i]=1; while(s[i-p[i]]==s[i+p[i]])p[i]++; if(ans<p[i])ans=p[i]; if(maxn<p[i]+i){ maxn=p[i]+i; id=i; } } /*printf("%s\n ",s); for(int i=1;i<=len*2+1;i++)printf("%d",p[i]);*/ return ans-1; } int main(){ memset(s,0,sizeof(s)); memset(p,0,sizeof(p)); gets(s); int ans=manacher(); printf("%d\n",ans); }