BZOJ 2342 双倍回文

发表于 | 更新于

Link

Solution

先 O(n2)O(n^2)的枚举策略是从一个#开始向两边扩展，在扩展过程中如果两个指针位置的回文串都足够长，就更新答案，直到l,rl,r的距离超过了以ii为中心的回文半径。足够长，指l+rad[l]−1≥i≥r−rad[r]+1l+rad[l]-1\ge i \ge r-rad[r]+1 做了什么无用功呢？如果从左往右找，只要找到第一个l+rad[l]−1≥il+rad[l]-1\ge i的点，那就一定找到了以ii为中心的最长双倍回文，因为右指针的回文串与左指针的在距离不超过ii的回文半径的时候指向的字符串是对称的。 那么现在要解决的就是如何快速找到最靠左的ll使得l≥i−rad[i]2,l+rad[l]−1≥il\ge i-\dfrac {rad[i]}2,l+rad[l]-1\ge i 然后这个是有单调性的：l+rad[l]−1<i⇒l+rad[l]−1<i+1l+rad[l]-1< i\Rightarrow l+rad[l]-1< i+1 所以就可以考虑用一个维护单调递增的数据结构来优化 应该可以用单调队列？似乎不能，因为rad[]rad[]并不单调 但是orz Stilwell 很神奇地用了并查集 复杂度O(nlogn)O(n\log n)?

Code

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
41
42
43
44
45
46
47
48
49
50
51
52
#include "lucida"
#include "lucida"
using std::min;
using std::copy;
const int MAXN=500000+11;
void Manacher(char *s,int &n,int rad[]) {
	static char ms[MAXN<<1]={'$'};
	for(int i=1;i<=n;++i) {
		ms[(i<<1)-1]='#';
		ms[i<<1]=s[i];
	}
	ms[++(n<<=1)]='#';
	ms[n+1]='@';copy(ms,ms+1+1+n,s);
	int mxp=0,mxr=0;
	for(int i=1;i<=n;++i) {
		rad[i]=i<=mxp+mxr-1?min(rad[2*mxp-i],mxp+mxr-i):1;
		while(s[i-rad[i]]==s[i+rad[i]]) 
			rad[i]++;
		if(i+rad[i]>mxp+mxr) {
			mxp=i;
			mxr=rad[i];
		}
	}
}
int fa[MAXN<<1];
int Root(int x) {
	return !fa[x]?x:fa[x]=Root(fa[x]);
}
int main() {
	freopen("input","r",stdin);
	static char s[MAXN<<1];
	static int rad[MAXN<<1];
	int n;is>>n>>(s+1);
	Manacher(s,n,rad);
	/*//x+rad[x]<=i+1<=x+rad[2*i-x]
	//找一个x最小的*/
	for(int i=2;i<=n;i+=2)
		fa[i]=i+1;//必须找偶数长度的
	int Ans=0;
	for(int i=1;i<=n;i+=2) {
		for(int j=Root(i-(rad[i]>>1));j<i;j=fa[j]=Root(j+1))
			if(j+rad[j]-1>=i) {
				chkmx(Ans,(i-j)*2);
				break;
			}
	}
	os<<Ans<<'\n';
	return 0;
}
/*
 4ms WA..没*2??
 */