最长回文（基础题hdu3068 马拉车）

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
Output
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
aaaa

abab
Sample Output
4
3

算是模板题吧，当作模板记一下。
先在每两个相邻字符中间插入一个分隔符，这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑.P［i］记录的是以字符s[i］为中心的最长回文串,记录以每个字符为中心的最长回文串的信息..

include <stdio.h>

include <string.h>

include

using namespace std;
char s[111000],s_new[211000];
int p[222000];
int init()
{
int i,j,l;
l=strlen(s);
s_new[0]='$',s_new[1]='#';
j=2;
for (i=0;i<l;i++)
{
s_new[j++]=s[i];
s_new[j++]='#';
}
s_new[j]='';
return j;
}
int manacher()
{
int len=init(),i,j;
int maxlen=-1,cent=0,right=0;

for (i=1;i<len;i++)
{
	if (i<right)
	p[i]=min(p[2*cent-i],right-i);//?
	else
	p[i]=1;
	while(s_new[i-p[i]]==s_new[i+p[i]])
	p[i]++;
	
	if (i+p[i]>right)
	{
		right=i+p[i];
		cent=i;
	}
	maxlen=max(maxlen,p[i]-1);
}
return maxlen;

}
int main()
{
while(~scanf("%s",s))
{
printf("%d ",manacher());
memset(s,0,sizeof(s));
memset(s_new,0,sizeof(s_new));
memset(p,0,sizeof(p));
}
return 0;
}