HDU3068(最长回文)

最长回文

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

思路

manacher模板题

1. 数组p[i]的定义：以i为中心的最长回文半径是多少；maxr的定义：目前所探索到的最右端点；id的定义：最长回文串的中心。

2. 第一个巧妙之处就解决了中心拓展法区分奇偶数的问题，通过空间增加一倍的空间复杂度将一个算法的时间复杂度直接降到线性。

3. 第二个巧妙之处就是灵活的运用了前面的计算结果。在计算以i为中心的最长回文长度时id 和 j为中心的回文串半径已经算过了。如果区间[j，i]是一个以id为中心的回文串时，那么[j，id] == [id，i]。所以在这种情况下我们只需要判断maxr - i的长度是否大于i - id的长度。如果大于那么就可以利用这个结果，如果小于那么说明以i为中心的回文串右区间伸出去了。没有探索所以只能在maxr - i 和 p[2*id-1]中取小的那一个，随后就是紧接着模拟中心拓展法进行两边拓展。
   

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int maxn = 110005;
char s[maxn<<1],str[maxn];
int p[maxn<<1];
int addstr(int n)
{
	int cnt = 0;
	s[cnt++] = '$';s[cnt++] = '#';
	for(int i = 0;i < n;i++){
		s[cnt++] = str[i];
		s[cnt++] = '#';
	}
	s[cnt] = '\0';
	return cnt;		//cnt = 2*strlen(str)+1
}
int manacher(int n)
{
	memset(p,0,sizeof(p));
	int maxr = 0,sum = 0,id = 0;
	for(int i = 0;i < n;i++){
		if(i > maxr)	p[i] = 1;
		else{								//在左区间[id，i] 和 右区间[i，maxr]取最小值。
			p[i] = min(maxr-i,p[2*id-i]);
		}
		while(s[i+p[i]] == s[i-p[i]]){		//类似中心拓展法
			p[i]++;
		}
		if(i+p[i] > maxr){					//更新最长回文中心和右边界
			id = i;
			maxr = i+p[i];
		}
		sum = max(sum,p[i]);				//记录最长回文长度。
	}
	return sum-1;	
}
int main()
{
	while(~scanf("%s",str)){
		int n = strlen(str);
		n = addstr(n);
		int ans = manacher(n);
		printf("%d\n",ans);
	}
	return 0;
} 

愿你走出半生，归来仍是少年~