BZOJ2565: 最长双回文串

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

HINT

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

对于100%的数据，2≤|S|≤10^5

2015.4.25新加数据一组

Manacher练手题，主要思想是开一个len数组表示当前下标结尾最长的回文子串长度，这样就可以在Manacher的过程中一边匹配一边类似dp的统计答案了。代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 5;
int len[maxn << 1], RL[maxn << 1], mx, cnt;
char words[maxn], s[maxn << 1];

void Manacher() {
	int Mr = 0, Mpos = 0, l, r;
	for(register int i = 0; i < cnt; ++i) {
		RL[i] = min(RL[(Mpos << 1) - i]/*对称位置*/, Mr - i/*长度超过目前范围*/);
		for(;(l = i - RL[i]) >= 0 && (r = i + RL[i]) < cnt && s[l] == s[r]; ++RL[i]) {
			if(l > 0) mx = max(mx, len[l - 1] + RL[i] * 2 + 1);
			len[i + RL[i]] = max(len[i + RL[i]], RL[i] * 2 + 1);		
		}
		--RL[i];
		if(Mr < i + RL[i]) Mpos = i, Mr = i + RL[i];
	}
}

int main() {
	scanf("%s", words);
	int sl = strlen(words);
	for(register int i = 0; i < sl; ++i)
		s[cnt++] = '#', s[cnt++] = words[i];
	s[cnt++] = '#';
	Manacher();
	printf("%d", (mx + 1) / 2);
	return 0;
}

Rockdu's Blog