题链：

http://poj.org/problem?id=3974

题解：

Manacher

求最长回文串长度。

终于会了传说中的马拉车，激动。
推荐一个很棒的博客：https://www.61mon.com/index.php/archives/181/

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 2005000

#define filein(x) freopen(#x".in","r",stdin);

#define fileout(x) freopen(#x".out","w",stdout);

using namespace std;

char T[MAXN]; int cnt;

int trans(char *S){

	int lS=strlen(S),lT=2;

	T[0]='&'; T[1]='#';

	for(int i=0;i<lS;i++){

		T[lT++]=S[i];

		T[lT++]='#';

	}

	return lT;

}

int Manacher(int N,char *S){

	static int p[MAXN],ans,pos,maxr;

	pos=maxr=ans=0;

	for(int i=1;i<N;i++){

		if(i<maxr) p[i]=min(p[2*pos-i],maxr-i);

		else p[i]=1;

		while(S[i+p[i]]==S[i-p[i]]) {

			if(i+p[i]>maxr){

				maxr=i+p[i],pos=i;

				if(S[i+p[i]-1]!='#')cnt++;

			}

			p[i]++;

		}

		ans=max(ans,p[i]-1);

	}

	return ans;

}

int main()

{

	static char S[MAXN],cas=0;

	while(1){

		scanf("%s",S);

		if(S[0]=='E'&&S[1]=='N'&&S[2]=='D'&&S[3]==0) break;

		int N=trans(S); cnt=0;

		int ans=Manacher(N,T);

		printf("Case %d: %d\n",++cas,ans);

	}

	return 0;

}