hihocoder1032：（manacher）

题目：http://hihocoder.com/PRoblemset/problem/1032

题目分析：manacher模板，RE了好多次。一开始是数组忘了开两倍长度，接下来又是多算了最后一位的答案导致数组越界（即’$’），重点是忘了写“if( i+temp[i]>p+temp[p] ) p=i;”这句如此重要的话……输出答案的时候要注意分类讨论一下。

CODE：

#include<iostream>#include<string>#include<cstring>#include<cmath>#include<cstdio>#include<cstdlib>#include<stdio.h>#include<algorithm>using namespace std;const int maxn=1000100;int temp[maxn<<1];string t,s;int n;int main(){	freopen("c.in","r",stdin);	freopen("c.out","w",stdout);		scanf("%d",&n);	for (int q=1; q<=n; q++)	{		cin>>t;		int tlen=t.size()-1;				s="";		s+='@';		for (int i=0; i<tlen; i++)		{			s+=t[i];			s+='#';		}		s+=t[tlen];		s+='$';				int slen=s.size();		int p=1,ans=0;		temp[0]=temp[1]=0;		for (int i=2; i<slen; i++)		{			temp[i]=max( 0,min( temp[2*p-i],p+temp[p]-i ) );			while ( s[i+temp[i]]==s[i-temp[i]-2] ) temp[i]++;			if ( i+temp[i]>p+temp[p] ) p=i;			if (s[i-1]=='#') ans=max(ans, temp[i]+(temp[i])%2 );			else ans=max(ans, temp[i]+(temp[i]-1)%2 );		}				printf("%d/n",ans);	}		return 0;}