洛谷题库 P4287 [SHOI2011]双倍回文 简略题解

洛谷题库 P4287 [SHOI2011]双倍回文

唉，还是没有考虑清楚细节。

容易发现，一个双倍回文串必定是一个回文串，同时前半段也是一个回文串。那么在使用Manacher算法求取每个字符对应的最长回文串时，就可以同步更新答案。

但一开始我写出这样的判断：

1
2
3
 // 完成第i个字符的最长回文的更新后
if (len[i] % 4 == 0 && len[i - (len[i] >> 1)] == len[i] / 2)
    ans = max (ans, len[i]);

然后喜提三个WA。检查了Manacher本身的正确性（甚至改变了开闭区间的写法）再交，仍旧不对。中午死活想不出哪里有误。直到看了题解的更新，才发现——最长双倍回文子串不一定是最长回文子串。例如，我们发现一个回文串$S = \textrm{aabaabaabaabaa}$，显然它自身不是双倍回文，但它的字串$S’=\textrm{abaabaabaaba}$是啊！

所以我们应当在每一次暴力扩展时（见代码）每扩展一位就检查是否满足双倍回文子串的性质。还有一点需要注意，检查该回文串前一半是否也是回文串时，同理不能看对应位置的最大回文半径。还是以上面的子串为例。有Manacher化后的串为$S_m = {\color{blue}\textrm{*a*a*b*a}}{\color{red}\textrm{*}}{\color{blue}\textrm{a*b*a*a*}}\textrm{b*a*a*b*a*a*}$（下标从0计数），则以红色的${\color{red}\textrm{*}}$为中心的最大回文串是蓝色部分，但在求取上述最大双倍回文串时只需要发现其子串$\textrm{a*b*a*a*b*a}$也是回文即可。所以应当看该字符的回文半径是否大于等于当前求取字符的回文半径的一半。

说起来有点绕？看代码！

R59102006 记录详情 （10次WA的惨痛教训）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 512000;
int n, R, C, rad[N<<1], ans;
char s[N<<1], _s[N];

int expand (int x, int l) { // 暴力扩展 
	while (x + l <= n<<1 && x - l >= 0
	  && s[x + l] == s[x - l]) { 
		++l; 
		if (x % 2 == 0 /* 双倍回文长度是4的倍数——显然其中心处在两个原字串字符的中间 */
		  && (l - 1) % 4 == 0 && rad[x - (l - 1) / 2] - 1 >= (l - 1) / 2 /* 按当前位置推算的回文串的1/4位置 */)
			ans = max (ans, l - 1); // 更新答案 
	}
	if (x + l > R)
		R = x + l, C = x; // 更新最长回文子串右端点和中心位置 
	return l;
}

void Manacher () {
	for (int i = 0; i <= n<<1; ++i) {
		if (i > R) rad[i] = expand (i, 1);
		else rad[i] = expand (i, min (rad[(C<<1) - i], R - i));
	}
}

int main () {
	/* P4287 [SHOI2011]双倍回文 吴秋实 */
	scanf ("%d", &n);
	scanf ("%s", _s);
	for (int i = 0; i <= n<<1; ++i)
		s[i] = i & 1 ? _s[i>>1] : '#';
	Manacher ();
	printf ("%d", ans);
	
	return 0;
}