本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
Description
Input
Output
Sample Input
abcbabcbabcba
abacacbaaaab
END
Sample Output
Case 1: 13
Case 2: 6
正解：manacher
解题报告：
manacher模板题。
网上有一篇博客写得很清楚：https://segmentfault.com/a/1190000003914228。
大致做法就是：维护一个目前所接触的最右端（不妨设为$maxRight$），和使得最长回文子串取到最右端的对称中心位置（不妨设为$id$），我们需要对于每个i求$p[i]$，$p[i]$表示以$i$为中心的最长回文串半径（包括$i$自身）。
每次处理i时，分类讨论：
如果$i>=maxRight$，显然$i$只能重新开始拓展，不能利用前面的结果，暴力比较即可；
如果$i<maxRight$，又可以分两种情况讨论，那篇博客里面说的很清楚了，分为$p[j]$很长和$p[j]$很短两种情况——总之就是可以利用之前的对于现在的$p[i]$确定一个初值，即$p[i]=min(p[2*id-i],p[maxRight-i])$。
容易发现最后$max(p[i]-1)$就是我们想求的答案。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 2000011;
const int MAXM = 1000011;
int len,n,p[MAXN],Case,ans,id,maxRight;
char ch[MAXM],s[MAXN];
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline void manacher(){
s[0]=‘%‘; s[1]=‘#‘; n=1;
for(int i=0;i<len;i++) {
s[++n]=ch[i];
s[++n]=‘#‘;//插入字符，化偶为奇
}
maxRight=0; id=0;
for(int i=1;i<=n;i++) {
//p[i]表示以i为中心的最长回文串半径（包括i）
if(i<maxRight) p[i]=min(p[2*id-i],maxRight-i); else p[i]=1;
for(;i+p[i]<=n && s[i-p[i]]==s[i+p[i]];p[i]++) ;
if(i+p[i]>maxRight) { id=i; maxRight=i+p[i]; }
}
for(int i=1;i<=n;i++) ans=max(ans,p[i]);
ans--;
}
inline void work(){
while(scanf("%s",ch)!=EOF) {
len=strlen(ch); if(len==3 && ch[0]==‘E‘ && ch[1]==‘N‘ && ch[2]==‘D‘) break;
memset(p,0,sizeof(p)); ans=1;
manacher(); Case++;
printf("Case %d: %d\n",Case,ans);
}
}
int main()
{
work();
return 0;
}
原文：http://www.cnblogs.com/ljh2000-jump/p/6264712.html