本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
正解：manacher
解题报告：
manacher裸题。
按题意所说的做就可以了，注意分奇数和偶数的情况讨论，当然也可以不讨论，弄出一个公共的式子即可。
开始没策清楚下标关系，WA了一发...
//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 = 400011;
int len,n,cha,p[MAXN],ans;
char ch[MAXN],s[MAXN],H;
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(){
memset(p,0,sizeof(p)); int maxR=0,id=0;
for(int i=1;i<=n;i++) {
if(i<maxR) p[i]=min(p[2*id-i],maxR-i); else p[i]=1;
for(;i+p[i]<=n && s[i-p[i]]==s[i+p[i]];p[i]++) ;
if(i+p[i]>maxR) { maxR=i+p[i]; id=i; }
}
}
inline void work(){
while(scanf("%s",ch)!=EOF) {
H=ch[0]; scanf("%s",ch); len=strlen(ch); n=1;
cha=H-‘a‘; s[0]=‘%‘; s[1]=‘#‘;
for(int i=0;i<len;i++) {
ch[i]-=cha; if(ch[i]<‘a‘) ch[i]+=26;
s[++n]=ch[i];
s[++n]=‘#‘;
}
manacher(); ans=1; int pos=1;
for(int i=1;i<=n;i++) if(p[i]>ans) ans=p[i],pos=i;
ans--; if(ans==1) { printf("No solution!\n"); continue; }
int l,r,mid;
if(pos%2==0) { mid=pos/2-1; l=mid-ans/2; r=mid+ans/2; }
else { mid=pos/2-1; l=mid-ans/2+1; r=mid+ans/2; }
printf("%d %d\n",l,r);
for(int i=l;i<=r;i++) printf("%c",ch[i]);
printf("\n");
}
}
int main()
{
work();
return 0;
}
原文：http://www.cnblogs.com/ljh2000-jump/p/6266316.html