[BZOJ 2342] [SHOI 2011] 双倍回文【Manacher+set+二分查找】

  • 2018-01-07
  • 0
  • 0

Problem:

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

记字符串 w 的倒置为 wR;例如 (abcd)R=dcba , (abba)R=abba 。
对字符串 x,如果 x 满足 xR=x,则称之为回文;例如 abba 是一个回文,而 abcd 不是。
如果 x 能够写成 wwRwwR的形式,则称它是一个“双倍回文”。换句话说,若要 x 是双倍回文,它的长度必须是 4 的倍数,而且 x、x 的前半部分、x 的后半部分都要是回文。例如: abbaabba 是一个双倍回文,而 abaaba 不是,因为它的长度不是 4 的倍数。
x 的子串是指在 x 中连续的一段字符所组成的字符串。例如 bc 是 abcd 的子串,而 ac 不是。
x 的回文子串,就是指满足回文性质的 x 的子串。
x 的双倍回文子串,就是指满足双倍回文性质的 x 的子串。
你的任务是,对于给定的字符串,计算它的最长双倍回文子串的长度。

Input

输入分为两行,第一行为一个整数,表示字符串的长度,第二行有个连续的小写的英文字符,表示字符串的内容。

Output

输出文件只有一行,即:输入数据中字符串的最长双倍回文子串的长度,如果双倍回文子串不存在,则输出0。

Sample Input

16
ggabaabaabaaball

Sample Output

12

HINT

N<=500000

Source

SHOI 2011

Solution:

这是一道加强版的 Manacher,并不只限于求最长回文子串了,而是加以变形,考查对限制条件的挖掘。

由于双倍回文子串本身一定是回文子串,而且其长度一定是偶数(更精确地说是 4 的倍数),所以不需要在间隔插入特殊字符,只需略微修改 Manacher 的代码即可。

首先用 Manacher 跑出以 str[i] 为中心的偶串的回文子串长度 pal[i]。

若用 X 表示双倍回文子串的中心偏左坐标(偶串中心在两字符之间),Y 表示该双倍回文子串右半部分的中心偏左坐标,则 X, Y 必须满足:

  • Y - pal[Y] ≤ X
  • X + pal[X] / 2 ≥ Y

因此我们可以先将 Y - pal[Y] 排序,再在从小到大枚举 X 的时候将符合 i) 的 Y 插入 set (或者手打平衡树。。反正我还不会打)中进行维护,再通过二分查找取得当前符合 ii) 的最大 Y 值,更新答案即可。在此我使用的是 set<Tp>.upper_bound(key) 的前驱来查找,当然也可以 set<Tp>.lower_bound(key, greater<Tp>()) 或是自己手打二分查找。

Code: O(nlog2n) [17304KB, 1072MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

int n, ans = 0;
char str[500005];
int pal[500005];

inline void Manacher(char *str, int len){
	str[0] = '$'; 
	int id = 0, mxr = 0;
	for(register int i = 1; i <= len; i++){
		pal[i] = (mxr >= i) ? min(mxr - i, pal[2 * id - i]) : 0;
		while(str[i + pal[i] + 1] == str[i - pal[i]]) pal[i]++;
		if(i + pal[i] > mxr) mxr = i + pal[i], id = i;
	}
}  // Needn't insert special characters because the length of required substring is even

int Y[500005], topY;
set<int> S;

inline bool cmp(const int &a, const int &b) {return a - pal[a] < b - pal[b];}

int main(){
	scanf("%d%s", &n, str + 1);
	Manacher(str, n);
	/*
		let X be the left-side center of double palindrome substring(DPS) "wwRwwR"
		let Y be the left-side center of the second "wwR" of the DPS
		X and Y must abide the following relationship:
			(1) Y - pal[Y] <= X
			(2) X + pal[X] / 2 >= Y
	*/
	for(register int i = 1; i <= n; i++) Y[i] = i;
	sort(Y + 1, Y + n + 1, cmp), topY = 1;
	for(register int X = 1; X <= n; X++){
		while(topY <= n && Y[topY] - pal[Y[topY]] <= X) S.insert(Y[topY++]);
		set<int>::iterator maxY = S.upper_bound(X + (pal[X] >> 1)); maxY--;
		ans = max(ans, *maxY - X << 2);
	}
	printf("%d\n", ans);
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai