HDU3068（Manacher算法求最大回文串，模板）

基本原理详见我的代码注释和http://www.cnblogs.com/hate13/p/4348751.html

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
char s[220050]; 
int p[220050];
int main()
{
	//freopen("t.txt","r",stdin);
	while(scanf("%s",s)!=EOF)
	{
		int l=strlen(s);
		for(int i=l;i>=0;i--)
		{
			s[i*2+2]=s[i];
			s[i*2+1]='#';
		}
		int id=0,m=0;
		s[0]='*';
		for(int i=2;i<=l*2;i++)
		{
			if(p[id]+id>i) p[i]=min(p[id-(i-id)],p[id]+id-i);//看id的右边界有没有超过i，超过了，那就不能借用前面已有的了，自己一个个去数 
			else p[i]=1;//表示只有自己一个点的半径 
			while(s[i-p[i]]==s[i+p[i]]) p[i]++;//如果还能向外扩张 
			if(id+p[id]<i+p[i]) id=i;//如果以i为中心的右边界更加远了 
			m=max(m,p[i]);
		}
		printf("%d\n",m-1);//半径-1就是子回文串长度 
	}
	return 0;
}