bzoj 2342 双倍回文

Posted on | Views:

$Manacher$ .

考虑用 $Manacher$ 预处理出每个位置的回文半径.

枚举双倍回文子串的中心 $i$ ,为了得到以 $i$ 为中心的最长双倍回文子串,需要找到左边第一个 $j+R(j)-1\ge i$ ,且 $R(i)\ge 2i-2j $ 的位置 $j$ ,这里的 $i,j​$ 在新串上的字符都必须为 ‘#’​ .

通过第二个条件可知 $j\ge \frac {2i-R(i)} {2}​$ ,即 $j\ge i-\lfloor \frac {R(i)} 2\rfloor​$ .

将所有 $j$ 按照 $j+R(j)-1$ 排序,从大到小枚举 $i$ ,将所有 $j+R(j)-1\ge i$ 的 $j$ 放入一个 $set$ 中.

此时在 $set$ 中查询 $i-\lfloor \frac {R(i)} 2\rfloor$ 的后继,就是要求的 $j$ ,注意特判不存在的情况以及检验 $j<i$ .

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e6+10;
char buf[MAXN],s[MAXN];
int n,R[MAXN];
int ans=0;
void Manacher()
{
	s[0]='$';
	for(int i=1;i<=n;++i)
	{
		s[2*i-1]='#';
		s[2*i]=buf[i];
	}
	s[2*n+1]='#';
	s[2*n+2]='@';
	n=2*n+2;
	int p=0,mx=0;
	for(int i=1;i<n;++i)
	{
		if(i>mx)
			R[i]=1;
		else
			R[i]=min(mx-i+1,R[2*p-i]);
		while(s[i-R[i]]==s[i+R[i]])
			++R[i];
		if(i+R[i]-1>mx)
			mx=i+R[i]-1,p=i;
	}
}
typedef pair<int,int> pii;
#define mp make_pair
set<int> S;
set<int>::iterator it;
pii tmp[MAXN];
int tot=0;
int main()
{
	n=read();
	scanf("%s",buf+1);
	Manacher();
	for(int j=1;j<n;++j)
		if(j&1)
			tmp[++tot]=mp(j+R[j]-1,j);
	sort(tmp+1,tmp+tot+1);
	int nx=tot;
	for(int i=n-1;i>=1;--i)
	{
		if(!(i&1))
			continue;
		while(nx>0 && tmp[nx].first>=i)
			S.insert(tmp[nx--].second);
		it=S.lower_bound(i-R[i]/2);
		if(it!=S.end() && *it<i)
			ans=max(ans,2*(i-*it));			
	}
	cout<<ans<<endl;
	return 0;
}