HDU - 3068 - 最长回文(裸马拉车)

个人博客

题目链接

题意：

给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等

题解：

裸的马拉车（Manacher）算法，直接上板子就够了。如果你没有马拉车板子，或者说你不会马拉车，请见Manacher最长回文串算法

代码：

#include<stdio.h>
#include<algorithm>
#include<cstring>
#define met(a) memset(a,0,sizeof(a));
using namespace std;
typedef long long ll;
const int maxn = 110050;
char s[maxn];
char s_new[maxn * 2];
int p[maxn * 2];
int Init(){
	int len = strlen(s);
	s_new[0] = '$';
	s_new[1] = '#';
	int j = 2;
	for (int i = 0; i < len; i++){
		s_new[j++] = s[i];
		s_new[j++] = '#';
	}
	s_new[j] = '\0';
	//printf("%s\n",s_new);
	return j;  //返回s_new的长度 
}
int Manacher(){
	int len = Init();  //取得新字符串长度并完成向s_new的转换 
	int maxLen = -1;   //最长回文长度 
	int id;
	int mx = 0;
	for (int i = 1; i < len; i++){
		if (i < mx)
			p[i] = min(p[2 * id - i], mx - i);  //需搞清楚上面那张图含义, mx和2*id-i的含义
		else
			p[i] = 1;
		while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断，因为左有'$',右有'\0' 
			p[i]++;
		//我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率 
		if (mx < i + p[i])  {
			id = i;
			mx = i + p[i];
		}
		maxLen = max(maxLen, p[i] - 1);
		// printf("%d %d %d\n",mx,id,maxLen);
	}
	/*for(int i=1;i<=len;i++)printf("%d ",p[i]); printf("\n");*/
	return maxLen;
}
int main(){
	while (scanf("%s", s)!=EOF){
		getchar();
		getchar();
		memset(p, 0, sizeof(p));
		if (s[0] == 'E'&&s[1] == 'N'&&s[2] == 'D')break;
		printf("%d\n",Manacher());
	}
	return 0;
}