HDU 3068 最长回文 (manacher算法)


最长回文

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 9188    Accepted Submission(s): 3159


Problem Description

给出一个只由小写英文字符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
 
Source
2009 Multi-University Training Contest 16 - Host by NIT


题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3068

题目分析:manacher算法是用来求解最长回文子串最简便的算法,下面最这个算法进行简要介绍:

定义数组p[i]表示以i为中心的(包含i这个字符)回文串半径长,将字符串s从前往后扫来计算p[i],最后最大的p[i]就是最长回文串长度,下面阐述如何求解p数组:

由于s是从前往后扫的,所以需要计算p[i]时一定已经计算好了p[1]....p[i - 1],假设现在扫描到了i + k这个位置,现在需要计算p[i + k],定义maxp是i + k位置前所有回文串中能延伸到的最右端的位置,maxp = p[i] + i

分两种情况:

1)i + k这个位置不在前面的任何回文串中,即i + k > maxp,则初始化p[i + k] = 1(即本身是回文串)然后将p[i + k]向左右延伸,

即while(s[i + k + p[i + k]] == s[i + k - p[i + k]])   p[i + k] ++

2)i + k这个位置被前面以位置i为中心的回文串包含,即maxp > i + k,这样p[i + k]就不从1开始,由回文串的性质可知i + k这个位置关于i与   i  - k对称,所以p[i + k]分为3种情况:


1. i - k回文串范围有一部分在p[i]之外,此时p[i + k] = p[i] - k,此时p[i + k]不可能更长,我们可以反证,假设还有一段d在之后,即

p[i + k] = p[i] - k + d,则根据回文性质可得此时得p[i] = p[i] + d,与p[i]矛盾,故不会更长。


2. i - k回文串范围全部在p[i]以内,此时p[i + k] = p[i - k],这个很显然


3. i - k回文串范围刚好等于p[i],此时p[i + k] = p[i - k],且可能继续向左右延伸,

即while(s[i + k + p[i + k]] == s[i + k - p[i + k]])   p[i + k] ++


综合上述所有情况,我们可以得到

p[i + k] = min(p[i - k], p[i] - k)

while(s[i + k + p[i + k]] == s[i + k - p[i + k]])  

         p[i + k] ++

最后遇到长度为偶数的字符串我们要将其长度变成奇数,穿插未出现的字符即可,防止数组越界,s[0]我们也要设置成一个与‘\0‘不同的字符

 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 110005;
char s[MAX << 1];
int p[MAX << 1];

int Manacher()
{
	int len = strlen(s), maxp = 0, ans = 0;
	for(int i = len; i >= 0; i--)
	{
		s[i * 2 + 2] = s[i];
		s[i * 2 + 1] = '#';
	}
	s[0] = '*';
	for(int i = 2; i < 2 * len + 1; i++)
	{
		if(p[maxp] + maxp > i)
			p[i] = min(p[2 * maxp - i], p[maxp] + maxp - i);
		else 
			p[i] = 1;
		while(s[i - p[i]] == s[i + p[i]])
			p[i]++;
		if(p[maxp] + maxp < i + p[i])
			maxp = i;
		if(ans < p[i])
			ans = p[i];
	}
	return ans - 1;
}

int main()
{
	while(scanf("%s", s) != EOF)
		printf("%d\n", Manacher());
}


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。