hdu3068 hihocoder 1032 最长回文子串 马拉车算法

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
char s1[maxn],s2[2*maxn];int p[2*maxn];
void gets2()
{
	int len=strlen(s1);
	s2[0]='%';
	for(int i=1;i<2*len;i+=2)
	{
		s2[i]='#';
		s2[i+1]=s1[i/2];
	}
	s2[2*len+1]='#';
	s2[2*len+2]='0';
	s2[2*len+3]='\0';
}
int main()
{
	while(~scanf("%s",&s1))
	{
		gets2();
		int len=strlen(s2);
		int mx=0,id=0,ans=0;int id_=0,len_=0;
		for(int i=1;i<=len;i++)
		{
			if(mx>=i) p[i]=min(p[2*id-i],mx-i);
			else p[i]=1;
			while(s2[i+p[i]]==s2[i-p[i]])
				p[i]++;
			if(p[i]+i>mx) mx=p[i]+i,id=i; 
			ans=max(ans,p[i]);
		}
		printf("%d\n",ans-1);
	}
	return 0;
}
           

好像没办法输出最长回文子串，容错率太低

借助添加字符，将字符串全部变成奇数个数，然后借助p数组，为i到右端回文端点的总长度，p[i]-1;即为回文长度

算法的本质即借助已经的出的回文长度来优化之后的扫描，外加一些暴力即可解决

重点在i与mx的讨论上，理解这一点就好说了